# Chromatic Properties of the Pancake Graphs

Discussiones Mathematicae Graph Theory (2017)

- Volume: 37, Issue: 3, page 777-787
- ISSN: 2083-5892

## Access Full Article

top## Abstract

top## How to cite

topElena 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 -

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.