Chromatic properties of the pancake graphs

Результат исследования: Научные публикации в периодических изданияхстатья

1 Цитирования (Scopus)


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
Номер выпуска3
СостояниеОпубликовано - авг 2017

Fingerprint Подробные сведения о темах исследования «Chromatic properties of the pancake graphs». Вместе они формируют уникальный семантический отпечаток (fingerprint).