The oriented chromatic number of the hexagonal grid is 6

The oriented chromatic number \(\chi_o(\overrightarrow{G})\) of an oriented graph \(\overrightarrow{G}\) is the smallest positive integer \(k\) such that there exists a homomorphism from \(\overrightarrow{G}\) to an orientation of the complete graph \(K_k\). The oriented chromatic number \(\chi_o(G)\) of an undirected graph \(G\) is defined as the maximum \(\chi_o(\overrightarrow{G})\) taken over all orientations \(\overrightarrow{G}\) of \(G\). If \(\mathcal{F} \) is a family of graphs, the oriented chromatic number \(\chi_o (\mathcal{F}) = \max\{\chi_o(G) \mid G \in\mathcal{F}\}\). Let \(H_{m,n}\) denote a hexagonal grid consisting of \(m\) rows of \(n\) hexagons, arranged in the staggered pattern characteristic of hexagonal tilings of the plane, and \(\mathcal{H}_2\) denote the set of all subgraphs of \(H_{m,n}\) for all values of \(m\) and \(n\). In [\textit{H. Bielak}, ``The oriented chromatic number of some grids, Ann. UMCS Inform. AI 5, 5--17 (2006)], it was shown that \( 5 \leq \chi_o(\mathcal{H}_2) \leq 6\). In this note, the author constructs a hexagonal grid with oriented chromatic number greater than 5, verified using a computer, thus proving that \( \chi_o (\mathcal{H}_2) = 6\). The author also provides an alternative proof that \(\chi_o(\mathcal{H}_2) \leq 6\).

Recommendations

Cites work

This page was built for publication: The oriented chromatic number of the hexagonal grid is 6

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6559398)