Properties, proved and conjectured, of Keller, Mycielski, and queen graphs

Witold Jarnicki, Wendy Myrvold, Peter Saltzman, Stan Wagon


We prove several results about three families of graphs. For queen graphs, defined from the usual moves of a chess queen, we find the edge-chromatic number in almost all cases. In the unproved case, we have a conjecture supported by a vast amount of computation, which involved the development of a new edge-coloring algorithm. The conjecture is that the edge-chromatic number is the maximum degree, except when simple arithmetic forces the edge-chromatic number to be one greater than the maximum degree. For Mycielski graphs, we strengthen an old result that the graphs are Hamiltonian by showing that they are Hamilton-connected (except M3, which is a cycle). For Keller graphs Gd, we establish, in all cases, the exact value of the chromatic number, the edge-chromatic number, and the independence number; and we get the clique covering number in all cases except 5 ≤ d ≤ 7. We also investigate Hamiltonian decompositions of Keller graphs, obtaining them up to G6.


Edge coloring, Keller graphs, Mycielski graphs, queen graphs, Hamiltonian, class one

Full Text:


ISSN: 1855-3974

Issues from Vol 6, No 1 onward are partially supported by the Slovenian Research Agency from the Call for co-financing of scientific periodical publications