Chromatic properties of the Pancake graphs | Zendy

Elena V. Konstantinova | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

Open Access

Chromatic properties of the Pancake graphs

Author(s) -

Elena V. Konstantinova

Publication year - 2017

Publication title -

discussiones mathematicae graph theory

Language(s) - English

Resource type - Journals

SCImago Journal Rank - 0.476

H-Index - 19

eISSN - 2083-5892

pISSN - 1234-3099

DOI - 10.7151/dmgt.1978

Subject(s) - combinatorics , chromatic scale , mathematics , upper and lower bounds , brooks' theorem , cayley graph , discrete mathematics , graph , chordal graph , 1 planar graph , mathematical analysis

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

The content you want is available to Zendy users.

Already have an account? Click here to sign in.

Having issues? You can contact us here

Accelerating Research