Colourings of oriented connected cubic graphs
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.
- A study on oriented relative clique number
- A theory of 2-dipath colourings
- Graph theory
- Homomorphism bounds for oriented planar graphs
- Homomorphisms and colourings of oriented graphs: an updated survey
- Oriented cliques and colorings of graphs with low maximum degree
- Oriented colourings of graphs with maximum degree three and four
- The chromatic number of oriented graphs
- Oriented colourings of graphs with maximum degree three and four
- Efficient computation of the oriented chromatic number of recursively defined digraphs
- Orientation spectra of cubic graphs
- On arc-coloring of subcubic graphs
- Perfect orientation colorings of cubic graphs
- Coloring graphs in oriented coloring of cubic graphs
- A generalization of Tait coloring cubic graphs
- scientific article; zbMATH DE number 3916298 (Why is no real title available?)
- Orientations and 3-colourings of graphs.
- Equitable oriented coloring
- Complexity of the oriented coloring in planar, cubic oriented graphs
- Oriented total-coloring of oriented graphs
- Adding direction constraints to the 1-2-3 conjecture
- The time complexity of oriented chromatic number for acyclic oriented connected subcubic subgraphs of grids
This page was built for publication: Colourings of oriented connected cubic graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q785820)
