Standard

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

в: Discussiones Mathematicae - Graph Theory, 22.09.2021.

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

Harvard

APA

Vancouver

Droogendijk L, Konstantinova EV. An improved bound on the chromatic number of the pancake graphs. Discussiones Mathematicae - Graph Theory. 2021 сент. 22. 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. 2021.

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",
author = "Leen Droogendijk and Konstantinova, {Elena V.}",
note = "Publisher Copyright: {\textcopyright} 2021 Leen Droogendijk et al., published by Sciendo 2021.",
year = "2021",
month = sep,
day = "22",
doi = "10.7151/dmgt.2432",
language = "English",
journal = "Discussiones Mathematicae - Graph Theory",
issn = "1234-3099",
publisher = "University of Zielona Gora",

}

RIS

TY - JOUR

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

AU - Droogendijk, Leen

AU - Konstantinova, Elena V.

N1 - Publisher Copyright: © 2021 Leen Droogendijk et al., published by Sciendo 2021.

PY - 2021/9/22

Y1 - 2021/9/22

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

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

U2 - 10.7151/dmgt.2432

DO - 10.7151/dmgt.2432

M3 - Article

AN - SCOPUS:85117416607

JO - Discussiones Mathematicae - Graph Theory

JF - Discussiones Mathematicae - Graph Theory

SN - 1234-3099

ER -

ID: 34562911