Chromatic Properties of the Pancake Graphs

• Autorzy: Elena Konstantinova
• Języki publikacji: EN

Abstrakty

EN

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 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.

Słowa kluczowe

EN

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

Kategorie tematyczne

• 05C25: Graphs and abstract algebra (groups, rings, fields, etc.)
• 05C15: Coloring of graphs and hypergraphs
• 05C69: Dominating sets, independent sets, cliques

• Wydawca: De Gruyter Open
• Czasopismo: Discussiones Mathematicae Graph Theory
• Rocznik: 2017
• Tom: 37
• Numer: 3
• Strony: 777-787

Daty

wydano

2017-08-01

otrzymano

2016-03-15

poprawiono

2016-07-12

zaakceptowano

2016-07-12

online

2017-07-06

Twórcy

autor

Elena Konstantinova

• , , , ; , , ,

Identyfikatory

DOI

10.7151/dmgt.1978