The list strengthening of the minimum-degree conjecture

From papers

Let G=(V,E)G=(V,E) be a graph. An \ell-list assignment is a map L:E2CL: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 k2k\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.

Progress summary

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

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).

Solutions 0

No solutions have been posted yet.