Equitable chromatic number conjecture for Pancake graphs

About 5 years old · traced to

For each integer n⩾2n\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 n⩾2n\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 n⩾2n\geqslant2 remains conjectural.

References

Primary source

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

Progress summary

Never refreshed

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

Solutions 0

No solutions have been posted yet.