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

Less than 1 year old · traced to

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

χ‾⩾(G−e)<χ‾⩾(G)<χ‾⩾(G−f).\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.

References

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.