The upper-bound conjecture for strong majority edge-colorings of admissible graphs

Let GG be an admissible graph, and let Maj(G){\mathrm Maj'}(G) denote the minimum number of colors in a strong majority edge-coloring of GG. Upper-bound conjecture.

If GG is an admissible graph, then

Maj(G)4.{\mathrm Maj'}(G)\le 4.

The conjecture proposes a substantial improvement of the upper bound established in the preceding theorem for strong majority edge-colorings. The supplied text gives no resolution, so its status remains open.

Sources & referencesView supporting material

Primary source

Rafał Kalinowski, Mateusz Kamyczura, Monika Pilśniak and Mariusz Woźniak, “Strong majority colorings of graphs”, arXiv:2605.23828 (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.