MathDB

List Colouring Conjecture

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 1

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).

Sources & referencesView supporting material

Primary source

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

edge-colouringgraph-colouringgraph-theorylist-colouring

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.