The minimum-degree conjecture for majority edge colourings

Let G=(V,E)G=(V,E) be a graph. A 1/k1/k-majority edge colouring with colour set CC is an edge colouring ω:EC\omega:E\to C such that, for every vertex vv and colour cCc\in C, the number dEc(v)d_{E_c}(v) of incident edges coloured cc satisfies dEc(v)d(v)/kd_{E_c}(v)\leq d(v)/k.

Majority edge-colouring conjecture. For every integer k2k\geq 2, if a graph GG has minimum degree δk2\delta\geq k^2, then GG is 1/k1/k-majority edge (k+1)(k+1)-colourable.

The bound is best possible up to the stated threshold because, for every k2k\geq 2, there is a graph of minimum degree k21k^2-1 without such a colouring. The conjecture is known for k=2,3,4k=2,3,4 and for bipartite graphs, but remains open in general.

Sources & referencesView supporting material

Primary source

Paweł Pękała and Jakub Przybyło, “On list extensions of the majority edge colourings”, arXiv:2502.12688 (2025).

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.