Journal article

Colourings of oriented connected cubic graphs

Christopher Duffy

DISCRETE MATHEMATICS | ELSEVIER | Published : 2020

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 oriented chromatic number for the family of orientations of connected cubic graphs equals the 2-dipath chromatic number or the long-standing conjecture of Sopena (Sopena, 1997) regarding the chromatic number of orientations of connected cubic graphs is false.

Grants

Funding Acknowledgements

Research supported by the Natural Science and Research Council of Canada.