- Tytuł:
- Chromatic Properties of the Pancake Graphs
- Autorzy:
- Konstantinova, Elena
- Powiązania:
- https://bibliotekanauki.pl/articles/31341647.pdf
- Data publikacji:
- 2017-08-01
- Wydawca:
- Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
- Tematy:
-
Pancake graph
Cayley graphs
symmetric group
chromatic number
total chromatic number - Opis:
- 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.
- Źródło:
-
Discussiones Mathematicae Graph Theory; 2017, 37, 3; 777-787
2083-5892 - Pojawia się w:
- Discussiones Mathematicae Graph Theory
- Dostawca treści:
- Biblioteka Nauki
Artykuł