The minimum-degree four conjecture for majority edge list colourings

About 1 year old · traced to

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.

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

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.