Oriented cliques and colorings of graphs with low maximum degree - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier
Journal Articles Discrete Mathematics Year : 2020

Oriented cliques and colorings of graphs with low maximum degree

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).
Fichier principal
Vignette du fichier
dops19.pdf (458.47 Ko) Télécharger le fichier
Origin Files produced by the author(s)

Dates and versions

lirmm-02938614 , version 1 (02-12-2020)

Identifiers

Cite

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

Altmetric

Share

More