Oriented cliques and colorings of graphs with low maximum degree
Janusz Dybizbański , Pascal Ochem , Alexandre Pinlou , Andrzej Szepietowski
AbstractAn oriented clique, or oclique, is an oriented graphGsuch that its oriented chromaticnumberχo(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, Duffyet al. (2019) by showing that for maximum degree 4, the maximum order of an ocliqueis equal to 12. For maximum degree 5, we prove that the maximum order of an ocliqueis between 16 and 18. In the same paper, Duffy et al. also proved that the orientedchromatic number ofconnectedoriented graphs with maximum degree 3 and 4 is atmost 9 and 69, respectively. We improve these results by showing that the orientedchromatic number ofnon-necessarily connectedoriented graphs with maximum degree3 (resp. 4) is at most 9 (resp. 26). The bound of 26 actually follows from a general resultwhich determines properties for a target graph to be universal for graphs of boundedmaximum 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).
|Journal series||Discrete Mathematics, ISSN 0012-365X, e-ISSN 1872-681X, (N/A 100 pkt)|
|Publication size in sheets||0.5|
|Keywords in English||oriented graph, homomorphism, oriented clique, bounded degree graph|
|Score||= 100.0, 04-02-2020, ArticleFromJournal|
|Publication indicators||: 2018 = 1.042; : 2018 = 0.728 (2) - 2018=0.756 (5)|
* presented citation count is obtained through Internet information analysis and it is close to the number calculated by the Publish or Perish system.