The Oriented Chromatic Number of the Hexagonal Grid is 6

2020/07/26 by Lozano, Antoni
#05C15 #05C85 #Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.2007.13111

Abstract

The oriented chromatic number of a directed graph G is the minimum order of an oriented graph to which G has a homomorphism. The oriented chromatic number χ_o(\cal F) of a graph family \cal F is the maximum oriented chromatic number over any orientation of any graph in \cal F. For the family of hexagonal grids \cal H₂, Bielak (2006) proved that 5 ≤ χ_o(\cal H₂) ≤ 6. Here we close the gap by showing that χ_o(\cal H₂) ≥ 6.

Related

• MAD Phase Transitions in the Oriented Chromatic Number
• Upper oriented chromatic number of undirected graphs and oriented colorings of product graphs
• Pushable chromatic number of graphs with degree constraints
• On Oriented Colourings of Graphs on Surfaces
• Oriented coloring of graphs with low maximum degree