Properties, proved and conjectured, of Keller, Mycielski, and queen graphs - Jarnicki, Witold (Ars mathematica contemporanea, 2017)
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 ?$M_3$?, which is a cycle). For Keller graphs ?$G_d$?, 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 ?$G_6$?.
Keywords: barvanje povezav; grafi Mycielskega; Kellerjevi grafi; kraljičini grafi