Chromatic properties of the Pancake graphs Pn, n ⩾ 2, that are Cayley graphs on the symmetric group Symn generated by prefix-reversals are investigated in the paper. It is proved that for any n ⩾ 3 the total chromatic number of Pn is n, and it is shown that the chromatic index of Pn is n − 1. We present upper bounds on the chromatic number of the Pancake graphs Pn, which improve Brooks’ bound for n ⩾ 7 and Katlin’s bound for n ⩽ 28. Algorithms of a total n-coloring and a proper (n − 1)-coloring are given.
@article{bwmeta1.element.doi-10_7151_dmgt_1978,
author = {Elena Konstantinova},
title = {Chromatic Properties of the Pancake Graphs},
journal = {Discussiones Mathematicae Graph Theory},
volume = {37},
year = {2017},
pages = {777-787},
language = {en},
url = {http://dml.mathdoc.fr/item/bwmeta1.element.doi-10_7151_dmgt_1978}
}
Elena Konstantinova. Chromatic Properties of the Pancake Graphs. Discussiones Mathematicae Graph Theory, Tome 37 (2017) pp. 777-787. http://gdmltest.u-ga.fr/item/bwmeta1.element.doi-10_7151_dmgt_1978/