Colourings of oriented connected cubic graphs

DOI10.1016/J.DISC.2020.112021MaRDI QIDQ785820zbMATH OpenOpenAlexFDO

Authors Christopher Duffy

Publication date 12 August 2020

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1908.02883

zbMATH Keywords

colouringhomomorphismoriented graphPaley tournament

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Coloring of graphs and hypergraphs (05C15) Connectivity (05C40)

Abstract: In this note we show every orientation of a connected cubic graph admits an oriented 8-colouring. This lowers the best-known upper bound for the chromatic number of the family of orientations of connected cubic graphs. We further show that every such oriented graph admits a 2-dipath 7-colouring. These results imply that either the chromatic number for the family of oriented connected cubic graphs equals the 2-dipath chromatic number or the long-standing conjecture of Sopena [Journal of Graph Theory 25:191-205 1997] regarding the chromatic number of orientations of connected cubic graphs is false.

Recommendations

• Coloring graphs in oriented coloring of cubic graphs
• Oriented colourings of graphs with maximum degree three and four
• Perfect orientation colorings of cubic graphs
• On arc-coloring of subcubic graphs
• Orientation spectra of cubic graphs

Cites work

• 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

Cited in

(13)

• Oriented total-coloring of oriented graphs
• Efficient computation of the oriented chromatic number of recursively defined digraphs
• On arc-coloring of subcubic graphs
• Adding direction constraints to the 1-2-3 conjecture
• Oriented colourings of graphs with maximum degree three and four
• Orientations and 3-colourings of graphs.
• Complexity of the oriented coloring in planar, cubic oriented graphs
• Orientation spectra of cubic graphs
• scientific article; zbMATH DE number 3916298 (Why is no real title available?)
• Perfect orientation colorings of cubic graphs
• Equitable oriented coloring
• Coloring graphs in oriented coloring of cubic graphs
• A generalization of Tait coloring cubic graphs

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)