Chromatic properties of the pancake graphs

Research output: Contribution to journalArticlepeer-review

1 Citation (Scopus)

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.

Original languageEnglish
Pages (from-to)777-787
Number of pages11
JournalDiscussiones Mathematicae - Graph Theory
Volume37
Issue number3
DOIs
Publication statusPublished - Aug 2017

Keywords

  • Cayley graphs
  • Chromatic number
  • Pancake graph
  • Symmetric group
  • Total chromatic number
  • NUMBER
  • total chromatic number
  • CYCLES
  • chromatic number
  • symmetric group

Fingerprint Dive into the research topics of 'Chromatic properties of the pancake graphs'. Together they form a unique fingerprint.

Cite this