An improved bound on the chromatic number of the pancake graphs

Leen Droogendijk, Elena V. Konstantinova

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

Аннотация

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.

Язык оригиналаанглийский
Число страниц12
ЖурналDiscussiones Mathematicae - Graph Theory
DOI
СостояниеОпубликовано - 22 сент. 2021

Предметные области OECD FOS+WOS

  • 1.01 МАТЕМАТИКА

Fingerprint

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

Цитировать