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.

In: Discussiones Mathematicae - Graph Theory, 22.09.2021.

Research output: Contribution to journal › Article › peer-review

Harvard

Droogendijk, L & Konstantinova, EV 2021, 'An improved bound on the chromatic number of the pancake graphs', Discussiones Mathematicae - Graph Theory. https://doi.org/10.7151/dmgt.2432

APA

Droogendijk, L., & Konstantinova, E. V. (2021). An improved bound on the chromatic number of the pancake graphs. Discussiones Mathematicae - Graph Theory. 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. 2021 Sept 22. doi: 10.7151/dmgt.2432

Author

Droogendijk, Leen ; Konstantinova, Elena V. / An improved bound on the chromatic number of the pancake graphs. In: 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.

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