Chromatic properties of the pancake graphs | Sciact - Система учета научной деятельности ИМ СО РАН

Chromatic properties of the pancake graphs Научная публикация

Журнал

Discussiones Mathematicae - Graph Theory
ISSN: 1234-3099 , E-ISSN: 2083-5892

Вых. Данные

Год: 2017, Том: 37, Номер: 3, Страницы: 777-787 Страниц : 11 DOI: 10.7151/dmgt.1978

Ключевые слова

Cayley graphs; Chromatic number; Pancake graph; Symmetric group; Total chromatic number

Авторы

Konstantinova E. ^1,2

Организации

1	Sobolev Institute of Mathematics, Novosibirsk, 630090, Russian Federation
2	Novosibirsk State University, Novosibirsk, 630090, Russian Federation

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.

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

Web of science:	WOS:000405312000019
Scopus:	2-s2.0-85021139640
OpenAlex:	W2612735421

БД	Цитирований
Scopus	6
OpenAlex	7
Web of science	4