The Oriented Chromatic Number of the Hexagonal Grid is 6

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 ${\chi }_o(\mathcal{F})$ of a graph family $\mathcal{F}$ is the maximum oriented chromatic number over any orientation of any graph in $\mathcal{F}$. For the family of hexagonal grids ${\mathcal{H}}_2$, Bielak (2006) proved that $5\le {\chi }_o({\mathcal{H}}_2)\le 6$. Here we close the gap by showing that ${\chi }_o({\mathcal{H}}_2)\ge 6$.

arXiv comment8 pages, 5 figures