Oriented cliques and colorings of graphs with low maximum degree

Janusz Dybizbański , Pascal Ochem , Alexandre Pinlou , Andrzej Szepietowski


An 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).
Author Janusz Dybizbański (FMPI / II)
Janusz Dybizbański,,
- Institute of Informatics
, Pascal Ochem
Pascal Ochem,,
, Alexandre Pinlou
Alexandre Pinlou,,
, Andrzej Szepietowski (FMPI / II)
Andrzej Szepietowski,,
- Institute of Informatics
Journal seriesDiscrete Mathematics, ISSN 0012-365X, e-ISSN 1872-681X, (N/A 100 pkt)
Issue year2020
Publication size in sheets0.5
Article number111829
Keywords in Englishoriented graph, homomorphism, oriented clique, bounded degree graph
ASJC Classification2607 Discrete Mathematics and Combinatorics; 2614 Theoretical Computer Science
URL https://doi.org/10.1016/j.disc.2020.111829
Languageen angielski
Score (nominal)100
Score sourcejournalList
ScoreMinisterial score = 100.0, 04-02-2020, ArticleFromJournal
Publication indicators Scopus SNIP (Source Normalised Impact per Paper): 2018 = 1.042; WoS Impact Factor: 2018 = 0.728 (2) - 2018=0.756 (5)
Citation count*
Share Share

Get link to the record

* presented citation count is obtained through Internet information analysis and it is close to the number calculated by the Publish or Perish system.
Are you sure?