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