Standard

Chromatic properties of the pancake graphs. / Konstantinova, Elena.

In: Discussiones Mathematicae - Graph Theory, Vol. 37, No. 3, 08.2017, p. 777-787.

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

Harvard

Konstantinova, E 2017, 'Chromatic properties of the pancake graphs', Discussiones Mathematicae - Graph Theory, vol. 37, no. 3, pp. 777-787. https://doi.org/10.7151/dmgt.1978

APA

Konstantinova, E. (2017). Chromatic properties of the pancake graphs. Discussiones Mathematicae - Graph Theory, 37(3), 777-787. https://doi.org/10.7151/dmgt.1978

Vancouver

Konstantinova E. Chromatic properties of the pancake graphs. Discussiones Mathematicae - Graph Theory. 2017 Aug;37(3):777-787. doi: 10.7151/dmgt.1978

Author

Konstantinova, Elena. / Chromatic properties of the pancake graphs. In: Discussiones Mathematicae - Graph Theory. 2017 ; Vol. 37, No. 3. pp. 777-787.

BibTeX

@article{588ee3d185cb4fd7ac82c624e652f354,
title = "Chromatic properties of the pancake graphs",
abstract = "Chromatic properties of the Pancake graphs Pn, n ≥ 2, that are Cayley graphs on the symmetric group Symn generated by prefix-reversals are in- vestigated in the paper. It is proved that for any n ≥ 3 the total chromatic number of Pn is n, and it is shown that the chromatic index of Pn is n - 1. We present upper bounds on the chromatic number of the Pancake graphs Pn, which improve Brooks' bound for n ≥ 7 and Katlin's bound for n ≤ 28. Algorithms of a total n-coloring and a proper (n - 1)-coloring are given.",
keywords = "Cayley graphs, Chromatic number, Pancake graph, Symmetric group, Total chromatic number, NUMBER, total chromatic number, CYCLES, chromatic number, symmetric group",
author = "Elena Konstantinova",
year = "2017",
month = aug,
doi = "10.7151/dmgt.1978",
language = "English",
volume = "37",
pages = "777--787",
journal = "Discussiones Mathematicae - Graph Theory",
issn = "1234-3099",
publisher = "University of Zielona Gora",
number = "3",

}

RIS

TY - JOUR

T1 - Chromatic properties of the pancake graphs

AU - Konstantinova, Elena

PY - 2017/8

Y1 - 2017/8

N2 - Chromatic properties of the Pancake graphs Pn, n ≥ 2, that are Cayley graphs on the symmetric group Symn generated by prefix-reversals are in- vestigated in the paper. It is proved that for any n ≥ 3 the total chromatic number of Pn is n, and it is shown that the chromatic index of Pn is n - 1. We present upper bounds on the chromatic number of the Pancake graphs Pn, which improve Brooks' bound for n ≥ 7 and Katlin's bound for n ≤ 28. Algorithms of a total n-coloring and a proper (n - 1)-coloring are given.

AB - Chromatic properties of the Pancake graphs Pn, n ≥ 2, that are Cayley graphs on the symmetric group Symn generated by prefix-reversals are in- vestigated in the paper. It is proved that for any n ≥ 3 the total chromatic number of Pn is n, and it is shown that the chromatic index of Pn is n - 1. We present upper bounds on the chromatic number of the Pancake graphs Pn, which improve Brooks' bound for n ≥ 7 and Katlin's bound for n ≤ 28. Algorithms of a total n-coloring and a proper (n - 1)-coloring are given.

KW - Cayley graphs

KW - Chromatic number

KW - Pancake graph

KW - Symmetric group

KW - Total chromatic number

KW - NUMBER

KW - total chromatic number

KW - CYCLES

KW - chromatic number

KW - symmetric group

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

U2 - 10.7151/dmgt.1978

DO - 10.7151/dmgt.1978

M3 - Article

AN - SCOPUS:85021139640

VL - 37

SP - 777

EP - 787

JO - Discussiones Mathematicae - Graph Theory

JF - Discussiones Mathematicae - Graph Theory

SN - 1234-3099

IS - 3

ER -

ID: 10184710