Chromatic properties of the pancake graphs Full article
| Journal |
Discussiones Mathematicae - Graph Theory
ISSN: 1234-3099 , E-ISSN: 2083-5892 |
||||
|---|---|---|---|---|---|
| Output data | Year: 2017, Volume: 37, Number: 3, Pages: 777-787 Pages count : 11 DOI: 10.7151/dmgt.1978 | ||||
| Tags | Cayley graphs; Chromatic number; Pancake graph; Symmetric group; Total chromatic number | ||||
| Authors |
|
||||
| Affiliations |
|
Abstract:
Chromatic properties of the Pancake graphs Pn, n ≥ 2, that are Cayley graphs on the symmetric group Symn generated by prefix-reversals are in- vestigated 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.
Cite:
Konstantinova E.
Chromatic properties of the pancake graphs
Discussiones Mathematicae - Graph Theory. 2017. V.37. N3. P.777-787. DOI: 10.7151/dmgt.1978 WOS Scopus OpenAlex
Chromatic properties of the pancake graphs
Discussiones Mathematicae - Graph Theory. 2017. V.37. N3. P.777-787. DOI: 10.7151/dmgt.1978 WOS Scopus OpenAlex
Identifiers:
| Web of science: | WOS:000405312000019 |
| Scopus: | 2-s2.0-85021139640 |
| OpenAlex: | W2612735421 |