Oriented Colourings of Graphs with Maximum Degree Three and Four

2018/12/13 by Duffy, Christopher, MacGillivray, Gary, Sopena, Eric · 1 citation
#05C20 #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics

paper · doi:10.48550/arxiv.1812.05510

Abstract

We show that any orientation of a graph with maximum degree three has an oriented 9-colouring, and that any orientation of a graph with maximum degree four has an oriented 69-colouring. These results improve the best known upper bounds of 11 and 80, respectively.

Cited by

• MAD Phase Transitions in the Oriented Chromatic Number

Related

• Oriented coloring of graphs with low maximum degree
• Oriented Colouring Graphs of Bounded Degree and Degeneracy
• MAD Phase Transitions in the Oriented Chromatic Number
• On parsimonious edge-colouring of graphs with maximum degree three
• Edge-colouring and orientations: applications to degree- and χ-boundedness