Oriented cliques and colorings of graphs with low maximum degree

Overview & Synopsis

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).