The minimum-degree conjecture for majority edge colourings
Let be a graph. A -majority edge colouring with colour set is an edge colouring such that, for every vertex and colour , the number of incident edges coloured satisfies .
Majority edge-colouring conjecture. For every integer , if a graph has minimum degree , then is -majority edge -colourable.
The bound is best possible up to the stated threshold because, for every , there is a graph of minimum degree without such a colouring. The conjecture is known for and for bipartite graphs, but remains open in general.
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
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.