The minimum-degree four conjecture for majority edge list colourings
The minimum-degree four conjecture for majority edge list colourings
Let be a graph with minimum degree at least . A list assignment gives each edge a list of colours, and a majority edge colouring from these lists assigns to every edge a colour from its list such that, at every vertex, no colour is used on more than half of the incident edges.
Minimum-degree four conjecture. Every graph with minimum degree at least admits a majority edge colouring from lists of size .
This conjecture strengthens the known result that every graph without pendant edges admits a majority edge colouring from lists of size . The source does not state whether the conjecture has been resolved.
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.