The list strengthening of the minimum-degree conjecture

About 1 year old · traced to

Let G=(V,E)G=(V,E) be a graph. An ℓ\ell-list assignment is a map L:E→2CL:E\to 2^C with ∣L(e)∣=ℓ|L(e)|=\ell for every edge. An LL-colouring is an edge colouring using a colour from each edge's list, and it is a 1/k1/k-majority edge colouring if dEc(v)≤d(v)/kd_{E_c}(v)\leq d(v)/k for every vertex vv and colour cc.

List strengthening conjecture. For every integer k≥2k\geq 2, if a graph GG has minimum degree δ(G)≥k2\delta(G)\geq k^2, then GG has a 1/k1/k-majority edge colouring from any lists of size k+1k+1.

This directly strengthens the minimum-degree conjecture for unrestricted colours and is supported by the regular-graph result proved in the paper. The general statement remains open.

References

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.