The minimum-degree four conjecture for majority edge list colourings

Let GG be a graph with minimum degree at least 44. 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 44 admits a majority edge colouring from lists of size 33.

This conjecture strengthens the known result that every graph without pendant edges admits a majority edge colouring from lists of size 44. 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

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.