Chromatic Properties of the Pancake Graphs
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 pre...
| Main Author: | |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
University of Zielona Góra
2017-08-01
|
| Series: | Discussiones Mathematicae Graph Theory |
| Subjects: | |
| Online Access: | https://doi.org/10.7151/dmgt.1978 |
| _version_ | 1797757701183242240 |
|---|---|
| author | Konstantinova Elena |
| author_facet | Konstantinova Elena |
| author_sort | Konstantinova Elena |
| collection | DOAJ |
| description | 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. |
| first_indexed | 2024-03-12T18:19:22Z |
| format | Article |
| id | doaj.art-8d99700f871749f1b42f4d5369ab09bf |
| institution | Directory Open Access Journal |
| issn | 2083-5892 |
| language | English |
| last_indexed | 2024-03-12T18:19:22Z |
| publishDate | 2017-08-01 |
| publisher | University of Zielona Góra |
| record_format | Article |
| series | Discussiones Mathematicae Graph Theory |
| spelling | doaj.art-8d99700f871749f1b42f4d5369ab09bf2023-08-02T08:59:14ZengUniversity of Zielona GóraDiscussiones Mathematicae Graph Theory2083-58922017-08-0137377778710.7151/dmgt.1978dmgt.1978Chromatic Properties of the Pancake GraphsKonstantinova Elena0Sobolev Institute of Mathematics, Novosibirsk, 630090, Russian Federation; Novosibirsk State University, Novosibirsk, 630090, Russian FederationChromatic 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.https://doi.org/10.7151/dmgt.1978pancake graphcayley graphssymmetric groupchromatic numbertotal chromatic number05c1505c2505c69 |
| spellingShingle | Konstantinova Elena Chromatic Properties of the Pancake Graphs Discussiones Mathematicae Graph Theory pancake graph cayley graphs symmetric group chromatic number total chromatic number 05c15 05c25 05c69 |
| title | Chromatic Properties of the Pancake Graphs |
| title_full | Chromatic Properties of the Pancake Graphs |
| title_fullStr | Chromatic Properties of the Pancake Graphs |
| title_full_unstemmed | Chromatic Properties of the Pancake Graphs |
| title_short | Chromatic Properties of the Pancake Graphs |
| title_sort | chromatic properties of the pancake graphs |
| topic | pancake graph cayley graphs symmetric group chromatic number total chromatic number 05c15 05c25 05c69 |
| url | https://doi.org/10.7151/dmgt.1978 |
| work_keys_str_mv | AT konstantinovaelena chromaticpropertiesofthepancakegraphs |