An improved bound on the chromatic number of the pancake graphs | Sciact - Система учета научной деятельности ИМ СО РАН

An improved bound on the chromatic number of the pancake graphs Научная публикация

Журнал

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

Вых. Данные

Год: 2024, Том: 44, Номер: 1, Страницы: 35-46 Страниц : 12 DOI: 10.7151/dmgt.2432

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

Chromatic number; Equitable coloring; Pancake graph

Авторы

Droogendijk L. ² , Konstantinova E.V. ^1,2

Организации

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

Информация о финансировании (1)

Министерство науки и высшего образования РФ
Математический центр в Академгородке

075-15-2019-1613, 075-15-2022-281

In this paper, an improved bound on the chromatic number of the Pancake graph Pn, n ≥ 9, is presented. The bound is obtained using a subadditivity property of the chromatic number of the Pancake graph. We also investigate an equitable coloring of Pn. An equitable (n - 1)-coloring based on efficient dominating sets is given and optimal equitable 4-colorings are considered for small n. It is conjectured that the chromatic number of Pn coincides with its equitable chromatic number for any n ≥ 2.

Droogendijk L. , Konstantinova E.V.
An improved bound on the chromatic number of the pancake graphs
Discussiones Mathematicae - Graph Theory. 2024. V.44. N1. P.35-46. DOI: 10.7151/dmgt.2432 WOS Scopus РИНЦ OpenAlex

Поступила в редакцию:	15 мар. 2021 г.
Принята к публикации:	10 сент. 2021 г.
Опубликована online:	22 сент. 2021 г.
Опубликована в печати:	6 мар. 2024 г.

Web of science:	WOS:000737388900004
Scopus:	2-s2.0-85117416607
РИНЦ:	47514678
OpenAlex:	W3199246168

Пока нет цитирований