Аннотация
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.
Язык оригинала | английский |
---|---|
Страницы (с-по) | 777-787 |
Число страниц | 11 |
Журнал | Discussiones Mathematicae - Graph Theory |
Том | 37 |
Номер выпуска | 3 |
DOI | |
Состояние | Опубликовано - авг 2017 |