MathDB

List Colouring Conjecture

About 6 years old · traced to

Let GG be a graph of maximum degree Δ\Delta. Let E(G)E(G) denote its edge set, and let LL be a list assignment assigning a set of colours L(e)L(e) to each edge ee of GG. An LL-colouring is a proper edge-colouring in which the colour assigned to each edge ee belongs to L(e)L(e).

List Colouring Conjecture. If GG is a graph of maximum degree Δ\Delta and LL is a list assignment to E(G)E(G) such that

∣L(e)∣≥Δ+1|L(e)|\geq \Delta+1

for every edge ee of GG, then there exists an LL-colouring of the edges of GG.

This is the edge-colouring list analogue of the chromatic index bound, and the paper describes it as a conjecture connected to linear arboricity. The supplied text gives no resolution status for this conjecture.

Equivalent formulations 1Other wordings

Other statements of this same problem, merged from separate entries. Each is equivalent to the statement above — proving any one settles them all.

  1. The list colouring conjecture

    For a graph GG, let χ′(G)\chi'(G) denote its edge chromatic number and let ch⁡′(G)\operatorname{ch}'(G) denote its list chromatic index. List colouring conjecture. For all graphs GG,

    ch⁡′(G)=χ′(G).\operatorname{ch}'(G)=\chi'(G).

    This is a central open question in list colouring, suggested independently by several researchers in the late 1970s and first appearing in print in 1985. If true, it would imply the bound χ”(G)≤Δ(G)+3\chi”(G)\leq\Delta(G)+3 for all graphs GG; the conjecture itself remains open.

    source: Richard Lang, “A note on total and list edge-colouring of graphs of tree-width 3”, arXiv:1504.05252 (2015).

References

Primary source

Richard Lang and Luke Postle, “An Improved Bound for the Linear Arboricity Conjecture”, arXiv:2008.04251 (2023).

edge-colouringgraph-colouringgraph-theorylist-colouring
Posted

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.