An improved bound on the chromatic number of the pancake graphs Full article
| Journal |
Discussiones Mathematicae - Graph Theory
ISSN: 1234-3099 , E-ISSN: 2083-5892 |
||||
|---|---|---|---|---|---|
| Output data | Year: 2024, Volume: 44, Number: 1, Pages: 35-46 Pages count : 12 DOI: 10.7151/dmgt.2432 | ||||
| Tags | Chromatic number; Equitable coloring; Pancake graph | ||||
| Authors |
|
||||
| Affiliations |
|
Funding (1)
| 1 |
Министерство науки и высшего образования РФ Mathematical Center in Akademgorodok |
075-15-2019-1613, 075-15-2022-281 |
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.
Cite:
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
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
Dates:
| Submitted: | Mar 15, 2021 |
| Accepted: | Sep 10, 2021 |
| Published online: | Sep 22, 2021 |
| Published print: | Mar 6, 2024 |
Identifiers:
| Web of science: | WOS:000737388900004 |
| Scopus: | 2-s2.0-85117416607 |
| Elibrary: | 47514678 |
| OpenAlex: | W3199246168 |
Citing:
Пока нет цитирований