Skip to Main content Skip to Navigation
Journal articles

Oriented cliques and colorings of graphs with low maximum degree

Janusz Dybizbański 1 Pascal Ochem 2 Alexandre Pinlou 2 Andrzej Szepietowski 1
2 ALGCO - Algorithmes, Graphes et Combinatoire
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
Abstract : An oriented clique, or oclique, is an oriented graph $G$ such that its oriented chromatic number $Xo(G)$ equals its order $|V(G)|$. We disprove a conjecture of Duffy, MacGillivray, and Sopena [Oriented colourings of graphs with maximum degree three and four, Duffy et al. (2019) by showing that for maximum degree 4, the maximum order of an oclique is equal to 12. For maximum degree 5, we prove that the maximum order of an oclique is between 16 and 18. In the same paper, Duffy et al. also proved that the oriented chromatic number of connected oriented graphs with maximum degree 3 and 4 is at most 9 and 69, respectively. We improve these results by showing that the oriented chromatic number of non-necessarily connected oriented graphs with maximum degree 3 (resp. 4) is at most 9 (resp. 26). The bound of 26 actually follows from a general result which determines properties for a target graph to be universal for graphs of bounded maximum degree. This generalization also allows us to get the upper bound of 90 (resp. 306, 1322) for the oriented chromatic number of graphs with maximum degree 5 (resp. 6, 7).
Complete list of metadatas

https://hal-lirmm.ccsd.cnrs.fr/lirmm-02938614
Contributor : Alexandre Pinlou <>
Submitted on : Tuesday, September 15, 2020 - 9:12:28 AM
Last modification on : Thursday, September 17, 2020 - 3:28:03 AM

Identifiers

Collections

Citation

Janusz Dybizbański, Pascal Ochem, Alexandre Pinlou, Andrzej Szepietowski. Oriented cliques and colorings of graphs with low maximum degree. Discrete Mathematics, Elsevier, 2020, 343 (5), pp.#111829. ⟨10.1016/j.disc.2020.111829⟩. ⟨lirmm-02938614⟩

Share

Metrics

Record views

16