The mixed edge-deletion conjecture for majority C-chromatic edge-critical graphs

Let GG be an χ\overline{\chi}_{\geqslant}-edge-critical graph with at least two edges, and let e,fE(G)e,f\in E(G). The mixed edge-deletion conjecture. It is impossible that

χ(Ge)<χ(G)<χ(Gf).\overline{\chi}_{\geqslant}(G-e)<\overline{\chi}_{\geqslant}(G)<\overline{\chi}_{\geqslant}(G-f).

The claim concerns whether edge deletions from an edge-critical graph can produce both a decrease and an increase in the majority CC-chromatic number. The supplied text does not state whether this has been resolved.

Sources & referencesView supporting material

Primary source

Csilla Bujtas, Magda Dettlaff, Hanna Furmanczyk and Aleksandra Laskowska, “Majority C-coloring of graphs”, arXiv:2604.20752 (2026).

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.