The minimum-degree conjecture for majority edge colourings
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.
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
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.