Chromatic properties of the pancake graphs

Elena Konstantinova

doi:10.7151/dmgt.1978

Chromatic properties of the pancake graphs

Elena Konstantinova

Кафедра теоретической кибернетики ММФ

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

1 Цитирования (Scopus)

Аннотация

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.

Язык оригинала	английский
Страницы (с-по)	777-787
Число страниц	11
Журнал	Discussiones Mathematicae - Graph Theory
Том	37
Номер выпуска	3
DOI	https://doi.org/10.7151/dmgt.1978
Состояние	Опубликовано - авг 2017

Доступ к документу

10.7151/dmgt.1978

Link to publication in Scopus

Fingerprint Подробные сведения о темах исследования «Chromatic properties of the pancake graphs». Вместе они формируют уникальный семантический отпечаток (fingerprint).

Цитировать

@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",

}

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 -