Geodesic
Properties, proved and conjectured, of Keller, Mycielski, and queen graphs
Ars Mathematica Contemporanea, Tome 13 (2017) no. 2, pp. 427-460.

Voir la notice de l'article provenant de la source Ars Mathematica Contemporanea website

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.
DOI : 10.26493/1855-3974.1143.844
Keywords: Edge coloring, Keller graphs, Mycielski graphs, queen graphs, Hamiltonian, class one 
@article{10_26493_1855_3974_1143_844,
     author = {Witold Jarnicki and Wendy Myrvold and Peter Saltzman and Stan Wagon},
     title = {Properties, proved and conjectured, of {Keller,} {Mycielski,} and queen graphs},
     journal = {Ars Mathematica Contemporanea},
     pages = {427--460},
     publisher = {mathdoc},
     volume = {13},
     number = {2},
     year = {2017},
     doi = {10.26493/1855-3974.1143.844},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.26493/1855-3974.1143.844/}
}
TY  - JOUR
AU  - Witold Jarnicki
AU  - Wendy Myrvold
AU  - Peter Saltzman
AU  - Stan Wagon
TI  - Properties, proved and conjectured, of Keller, Mycielski, and queen graphs
JO  - Ars Mathematica Contemporanea
PY  - 2017
SP  - 427
EP  - 460
VL  - 13
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.26493/1855-3974.1143.844/
DO  - 10.26493/1855-3974.1143.844
LA  - en
ID  - 10_26493_1855_3974_1143_844
ER  - 
%0 Journal Article
%A Witold Jarnicki
%A Wendy Myrvold
%A Peter Saltzman
%A Stan Wagon
%T Properties, proved and conjectured, of Keller, Mycielski, and queen graphs
%J Ars Mathematica Contemporanea
%D 2017
%P 427-460
%V 13
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.26493/1855-3974.1143.844/
%R 10.26493/1855-3974.1143.844
%G en
%F 10_26493_1855_3974_1143_844
Witold Jarnicki; Wendy Myrvold; Peter Saltzman; Stan Wagon. Properties, proved and conjectured, of Keller, Mycielski, and queen graphs. Ars Mathematica Contemporanea, Tome 13 (2017) no. 2, pp. 427-460. doi : 10.26493/1855-3974.1143.844. http://geodesic.mathdoc.fr/articles/10.26493/1855-3974.1143.844/

Cité par Sources :