
arXiv: 1411.7192
AbstractThe clique number of an undirected graph G is the maximum order of a complete subgraph of G and is a well‐known lower bound for the chromatic number of G. Every proper k‐coloring of G may be viewed as a homomorphism (an edge‐preserving vertex mapping) of G to the complete graph of order k. By considering homomorphisms of oriented graphs (digraphs without cycles of length at most 2), we get a natural notion of (oriented) colorings and oriented chromatic number of oriented graphs. An oriented clique is then an oriented graph whose number of vertices and oriented chromatic number coincide. However, the structure of oriented cliques is much less understood than in the undirected case. In this article, we study the structure of outerplanar and planar oriented cliques. We first provide a list of 11 graphs and prove that an outerplanar graph can be oriented as an oriented clique if and only if it contains one of these graphs as a spanning subgraph. Klostermeyer and MacGillivray conjectured that the order of a planar oriented clique is at most 15, which was later proved by Sen. We show that any planar oriented clique on 15 vertices must contain a particular oriented graph as a spanning subgraph, thus reproving the above conjecture. We also provide tight upper bounds for the order of planar oriented cliques of girth k for all .
FOS: Computer and information sciences, homomorphism, Discrete Mathematics (cs.DM), oriented graph, planar graph, Planar graphs; geometric and topological aspects of graph theory, Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.), Coloring of graphs and hypergraphs, oriented clique, FOS: Mathematics, Mathematics - Combinatorics, Combinatorics (math.CO), coloring, Computer Science - Discrete Mathematics
FOS: Computer and information sciences, homomorphism, Discrete Mathematics (cs.DM), oriented graph, planar graph, Planar graphs; geometric and topological aspects of graph theory, Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.), Coloring of graphs and hypergraphs, oriented clique, FOS: Mathematics, Mathematics - Combinatorics, Combinatorics (math.CO), coloring, Computer Science - Discrete Mathematics
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 15 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Top 10% | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Top 10% | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Top 10% |
