Outerplanar and planar oriented cliques

DOI10.1002/JGT.21893MaRDI QIDQ2811201zbMATH OpenOpenAlexFDO

Authors Ayan Nandy, Sagnik Sen, Éric Sopena

Publication date 10 June 2016

Published in Journal of Graph Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1411.7192

zbMATH Keywords

homomorphismoriented graphplanar graphcoloringoriented clique

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Planar graphs; geometric and topological aspects of graph theory (05C10) Coloring of graphs and hypergraphs (05C15)

Abstract: The 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 paper, 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 [S. Sen. Maximum Order of a Planar Oclique Is 15. Proc. IWOCA'2012. {em Lecture Notes Comput. Sci.} 7643:130--142]. 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 $kge4$.

Recommendations

• Analogues of cliques for oriented coloring
• A study on oriented relative clique number
• On oriented relative clique number
• Oriented coloring of triangle-free planar graphs and 2-outerplanar graphs
• On push chromatic number of planar graphs and planar \(p\)-cliques

Cites work

• Analogues of cliques for oriented coloring
• Distances in orientations of graphs
• Domination in planar graphs with small diameter*
• Good and semi-strong colorings of oriented planar graphs
• Minimal oriented graphs of diameter 2
• Oriented graph coloring
• The chromatic number of oriented graphs
• The complexity of deciding whether a graph admits an orientation with fixed weak diameter
• The monadic second order logic of graphs. VI: On several representations of graphs by relational structures

Cited in

(19)

• On oriented cliques with respect to push operation
• Analogues of cliques for oriented coloring
• A homomorphic polynomial for oriented graphs
• Homomorphisms and colourings of oriented graphs: an updated survey
• Clustered Planarity: Clusters with Few Outgoing Edges
• Pushable chromatic number of graphs with maximum average degree at most \(\frac{14}{5}\)
• Oriented total-coloring of oriented graphs
• Classification of edge-critical underlying absolute planar cliques for signed graphs
• On fractional version of oriented coloring
• On deeply critical oriented cliques
• Analogues of cliques for \((m,n)\)-colored mixed graphs
• Maximum order of a planar oclique is 15
• On coloring parameters of triangle-free planar \((n, m)\)-graphs
• On push chromatic number of planar graphs and planar \(p\)-cliques
• The relative oriented clique number of triangle-free planar graphs is 10
• Adding direction constraints to the 1-2-3 conjecture
• A study on oriented relative clique number
• Oriented cliques and colorings of graphs with low maximum degree
• On clique numbers of colored mixed graphs

This page was built for publication: Outerplanar and planar oriented cliques

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2811201)