Chromatic Properties of the Pancake Graphs

Elena Konstantinova. "Chromatic Properties of the Pancake Graphs." Discussiones Mathematicae Graph Theory 37.3 (2017): 777-787. <http://eudml.org/doc/288311>.

@article{ElenaKonstantinova2017,
abstract = {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.},
author = {Elena Konstantinova},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {Pancake graph; Cayley graphs; symmetric group; chromatic number; total chromatic number},
language = {eng},
number = {3},
pages = {777-787},
title = {Chromatic Properties of the Pancake Graphs},
url = {http://eudml.org/doc/288311},
volume = {37},
year = {2017},
}

TY - JOUR
AU - Elena Konstantinova
TI - Chromatic Properties of the Pancake Graphs
JO - Discussiones Mathematicae Graph Theory
PY - 2017
VL - 37
IS - 3
SP - 777
EP - 787
AB - 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.
LA - eng
KW - Pancake graph; Cayley graphs; symmetric group; chromatic number; total chromatic number
UR - http://eudml.org/doc/288311
ER -