An improved bound on the chromatic number of the pancake graphs

Standard

An improved bound on the chromatic number of the pancake graphs. / Droogendijk, Leen; Konstantinova, Elena V.

в: Discussiones Mathematicae - Graph Theory, Том 44, № 1, 2024, стр. 35-46.

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

Harvard

Droogendijk, L & Konstantinova, EV 2024, 'An improved bound on the chromatic number of the pancake graphs', Discussiones Mathematicae - Graph Theory, Том. 44, № 1, стр. 35-46. https://doi.org/10.7151/dmgt.2432

APA

Droogendijk, L., & Konstantinova, E. V. (2024). An improved bound on the chromatic number of the pancake graphs. Discussiones Mathematicae - Graph Theory, 44(1), 35-46. https://doi.org/10.7151/dmgt.2432

Vancouver

Droogendijk L, Konstantinova EV. An improved bound on the chromatic number of the pancake graphs. Discussiones Mathematicae - Graph Theory. 2024;44(1):35-46. doi: 10.7151/dmgt.2432

Author

Droogendijk, Leen ; Konstantinova, Elena V. / An improved bound on the chromatic number of the pancake graphs. в: Discussiones Mathematicae - Graph Theory. 2024 ; Том 44, № 1. стр. 35-46.

BibTeX

@article{5ce7bbbd2dc24a8c85e455da4596f453,

title = "An improved bound on the chromatic number of the pancake graphs",

abstract = "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. ",

keywords = "Chromatic number, Equitable coloring, Pancake graph, equitable coloring, chromatic number",

author = "Leen Droogendijk and Konstantinova, {Elena V.}",

note = "Publisher Copyright: {\textcopyright} 2021 Leen Droogendijk et al., published by Sciendo 2021.",

year = "2024",

doi = "10.7151/dmgt.2432",

language = "English",

volume = "44",

pages = "35--46",

journal = "Discussiones Mathematicae - Graph Theory",

issn = "1234-3099",

publisher = "University of Zielona Gora",

number = "1",

}

RIS

TY - JOUR

T1 - An improved bound on the chromatic number of the pancake graphs

AU - Droogendijk, Leen

AU - Konstantinova, Elena V.

PY - 2024

Y1 - 2024

N2 - 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.

AB - 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.

KW - Chromatic number

KW - Equitable coloring

KW - Pancake graph

KW - equitable coloring

KW - chromatic number

UR - http://www.scopus.com/inward/record.url?scp=85117416607&partnerID=8YFLogxK

UR - https://www.mendeley.com/catalogue/56c6fdc3-1c92-3754-aba9-0dc551342594/

U2 - 10.7151/dmgt.2432

DO - 10.7151/dmgt.2432

M3 - Article

AN - SCOPUS:85117416607

VL - 44

SP - 35

EP - 46

JO - Discussiones Mathematicae - Graph Theory

JF - Discussiones Mathematicae - Graph Theory

SN - 1234-3099

IS - 1

ER -

ID: 34562911