Equitable chromatic number conjecture for Pancake graphs

From papers

For each integer n2n\geqslant 2, let PnP_n be the Pancake graph, let χ(Pn)\chi(P_n) denote its chromatic number, and let χ=(Pn)\chi_{=}(P_n) denote its equitable chromatic number, the least number of colors in a proper coloring whose color-class sizes differ pairwise by at most one.

Pancake graph equitable coloring conjecture. For every n2n\geqslant 2,

χ(Pn)=χ=(Pn).\chi(P_n)=\chi_{=}(P_n).

Since equitable colorings are proper colorings with an additional balance condition, one always has χ(Pn)χ=(Pn)\chi(P_n)\leqslant\chi_{=}(P_n). The paper notes that the equality holds for the optimal colorings known there, while the assertion for all n2n\geqslant2 remains conjectural.

Progress summary

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Sources & referencesView supporting material

Primary source

Leen Droogendijk and Elena V. Konstantinova, “An improved bound on the chromatic number of the Pancake graphs”, arXiv:2103.11092 (2021).

Solutions 0

No solutions have been posted yet.