An improved bound on the chromatic number of the Pancake graphs

Abstract

In this paper an improved bound on the chromatic number of the Pancake graph $P_n,n⩾2$, is presented. The bound is obtained using a subadditivity property of the chromatic number of the Pancake graph. We also investigate an equitable coloring of $P_n$. An equitable $(n-1)$-coloring based on efficient dominating sets is given and optimal equitable $4$-colorings are considered for small $n$. It is conjectured that the chromatic number of $P_n$ coincides with its equitable chromatic number for any $n⩾2$.

References in corpus (1)

• Equitable partitions of Latin-square graphs