Equitable chromatic number conjecture for Pancake graphs
Equitable chromatic number conjecture for Pancake graphs
For each integer , let be the Pancake graph, let denote its chromatic number, and let 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 ,
Since equitable colorings are proper colorings with an additional balance condition, one always has . The paper notes that the equality holds for the optimal colorings known there, while the assertion for all 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
Sign in to submit a solution.
No solutions have been posted yet.