Majority 3-edge-coloring conjecture for graphs without pendant edges

A majority 33-edge-coloring of a graph is an edge-coloring with three colors in which, at every vertex, the number of incident edges of its most frequent color is at most the number of incident edges having other colors. A graph is Class 22 if its chromatic index exceeds its maximum degree. Majority 3-edge-coloring conjecture. Every graph GG without pendant edges admits a majority 33-edge-coloring unless GG contains, as an induced subgraph, a Class 22 graph HH with Δ(H)=3\Delta(H)=3 and with some vertices of HH having degree at most 33 in GG. The conjecture identifies subcubic Class 22 subgraphs as the only obstruction to majority 33-edge-colorability, extending the finite-graph conjecture to infinite graphs.

Sources & referencesView supporting material

Primary source

Rafał Kalinowski, Monika Pilśniak and Marcin Stawiski, “List majority edge-colorings of graphs”, arXiv:2312.00922 (2023).

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.