CHROMATIC PROPERTIES OF THE PANCAKE GRAPHS

被引：4

作者：

Konstantinova, Elena ^{[1
,2
]}

机构：

[1] Sobolev Inst Math, Novosibirsk 630090, Russia

[2] Novosibirsk State Univ, Novosibirsk 630090, Russia

来源：

DISCUSSIONES MATHEMATICAE GRAPH THEORY | 2017年 / 37卷 / 03期

关键词：

Pancake graph; Cayley graphs; symmetric group; chromatic number; total chromatic number; NUMBER; CYCLES;

D O I：

10.7151/dmgt.1978

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

Chromatic properties of the Pancake graphs Pn, n >= 2, that are Cayley graphs on the symmetric group Symn generated by prefix-reversals are investigated in the paper. It is proved that for any n >= 3 the total chromatic number of P-n 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 P-n, which improve Brooks bound for n >= 7 and Katlins bound for n >= 28. Algorithms of a total n-coloring and a proper (n - 1)-coloring are given.

引用

页码：777 / 787

页数：11

共 13 条

[1] UPPER BOUND OF A GRAPHS CHROMATIC NUMBER, DEPENDING ON GRAPHS DEGREE AND DENSITY [J].