论文标题
六边形网格的定向色数为6
The Oriented Chromatic Number of the Hexagonal Grid is 6
论文作者
论文摘要
定向图$ g $的定向色度是$ g $具有同构的定向图的最小顺序。图形系列$ {\ cal f} $的定向色度$χ_o（{\ cal f}）$是$ {\ cal f} $中任何图的任何方向上的最大定向色数。对于六边形网格的家族$ {\ cal H} _2 $，Bielak（2006）证明了$ 5 \leχ_o（{\ cal H} _2）\ le 6 $。在这里，我们通过显示$χ_o（{\ cal H} _2）\ ge 6 $来缩小差距。
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}_2$, Bielak (2006) proved that $5 \le χ_o({\cal H}_2) \le 6$. Here we close the gap by showing that $χ_o({\cal H}_2) \ge 6$.
