Oriented cliques and colorings of graphs with low maximum degree - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Accéder directement au contenu
Article Dans Une Revue Discrete Mathematics Année : 2020

Oriented cliques and colorings of graphs with low maximum degree

Résumé

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
Origine : Fichiers produits par l'(les) auteur(s)

Dates et versions

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

Identifiants

Citer

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⟩
67 Consultations
70 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More