## Problem of the Week 1166## The Hex QueenA hex board H(n) is a triangular board using hexagonal cells, with n cells on a side:
A hex queen can move along a row of adjacent cells in any of the three directions.
What is the smallest number of colors that can be assigned to the cells of Source: Dan Ullman and Stan Wagon. More: This problem seeks the chromatic number of HQ(14), the HexQueen graph on the 14-board. One wants to know more HQ parameters, and for all n. Here is a brief summary of what is and is not known for queens (there are also kings, bishops, and knights that are worthy of study). Hex Queen Summary: - regular: yes, degree d = 2n − 2.
- chromatic number: known for all n.
- fractional chromatic number: known for all n.
- independence number: known for all n; it is Floor[(2n + 1)/3)].
- largest clique and clique covering number are both, trivially, n.
- domination number, g (as in the classic problem of placing standard chess queens on a board so as to attack all squares, to which the answer is 5):
- edge chromatic number:
- Hamiltonian: easy
- Hamiltonian decomposition: appear to exist in all cases (and this implies the class 1 conjecture above).
For more, see Wikipedia. The pieces in true hexagonal chess are defined differently than I have done here. In particular, what is called a Hex Queen here is really a rook in the chess game. Mathematically, it seems that the true hexagonal chess pieces for king, bishop, and queen are not as interesting as the variants, since they do have nice geometric definitions. For example, one could consider a geometric kingas using nearest neighbors only; that graph is somewhat well studied and knownas the triangular grid graph. So from this point of view, the rook is the onlyone of the traditional hex chess pieces with a nice adjacency definition, and this problem probably should call the object of study the hex rook graph, as opposed to the hex queen graph. © Copyright 2013 Stan Wagon. Reproduced with permission. |

2 October 2013