Colourings of oriented connected cubic graphs (Q785820): Difference between revisions

A simple graph is cubic if its maximum degree is at most \(3\). An oriented graph is a digraph with directed girth at most \(3\). An oriented coloring of a digraph is a proper coloring of its vertices such that there are no two arcs whose endpoints receive the same pair of colors but with opposite colors to their respective tail vertices. A more relaxed notion is that of \(2\)-dipath coloring -- a \(2\)-dipath coloring of an oriented graph is a proper vertex-coloring such that the endpoints of every directed \(2\)-path receive distinct colors. The author shows that every oriented graph whose underlying undirected graph is connected and cubic, has an oriented \(8\)-coloring. Further, they show that every orientation of a cubic graph (not necessarily connected), has a \(2\)-dipath coloring with \(7\) colors. These results have relevance for resolving the old conjecture of \textit{E. Sopena} [J. Graph Theory 25, No. 3, 191--205 (1997; Zbl 0874.05026)], that orientations of connected cubic graphs have oriented colorings using at most \(7\) colors. In particular, they imply that either there exists an oriented connected cubic graph with oriented chromatic number equal to \(8\), i.e. the conjecture is false, or every orientation of any connected cubic graph has a \(2\)-dipath coloring as well as an oriented coloring using at most \(7\) colors. The results extend, and use, those of \textit{C. Duffy} et al. [Discrete Math. 342, No. 4, 959--974 (2019; Zbl 1405.05056)], where it was shown that every connected properly subcubic graph (cubic but not \(3\)-regular), with no degree \(3\) source vertex adjacent to a degree \(3\) sink vertex, has a homomorphism to the Paley tournament on \(7\) vertices, and therefore has oriented chromatic number at most \(7\). In a different direction, they are related to more recent work [\textit{J. Dybizbański} et al., ibid. 343, No. 5, Article ID 111829, 10 p. (2020; Zbl 1435.05073)] showing that every oriented cubic graph has an oriented \(9\)-coloring. The proofs work by first using the homomorphism to the Paley tournament shown in [Duffy et al., loc. cit.], on a slightly smaller subgraph and then extending it to the full graph using one extra color, via local perturbations and a structural lemma which the author proves. For the second result, on \(2\)-dipath colorings, some average counting arguments are also needed.