Outerplanar and planar oriented cliques

DOI10.1002/JGT.21893zbMATH Open1339.05081arXiv1411.7192OpenAlexW2963300251MaRDI QIDQ2811201FDOQ2811201

Authors: Ayan Nandy, Sagnik Sen, Éric Sopena 

Publication date: 10 June 2016

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

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$.

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

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

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)

Cites Work

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

Cited In (19)

• Analogues of cliques for oriented coloring
• A homomorphic polynomial for oriented graphs
• Homomorphisms and colourings of oriented graphs: an updated survey
• Pushable chromatic number of graphs with maximum average degree at most \(\frac{14}{5}\)
• Clustered Planarity: Clusters with Few Outgoing Edges
• Oriented total-coloring of oriented graphs
• Classification of edge-critical underlying absolute planar cliques for signed graphs
• On deeply critical oriented cliques
• On fractional version of oriented coloring
• 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
• On oriented cliques with respect to push operation

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)