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.
Original language | English |
---|---|
Pages (from-to) | 777-787 |
Number of pages | 11 |
Journal | Discussiones Mathematicae - Graph Theory |
Volume | 37 |
Issue number | 3 |
DOIs | |
Publication status | Published - Aug 2017 |
Keywords
- Cayley graphs
- Chromatic number
- Pancake graph
- Symmetric group
- Total chromatic number
- NUMBER
- total chromatic number
- CYCLES
- chromatic number
- symmetric group