Local Vizing's theorem

Let GG be a graph with a list assignment LL to the edges of GG. For every edge e=uve=uv, define its permissible colour list by

L(e)=max{1,,max{deg(u),deg(v)}+1}.L(e)=\max\{1,\dots,\max\{\deg(u),\deg(v)\}+1\}.

An LL-edge-colouring assigns to each edge a colour from its list so that incident edges receive distinct colours.

Local Vizing's theorem. There is an LL-edge-colouring of GG.

Vizing's theorem gives an edge-colouring from a common list of size Δ(G)+1\Delta(G)+1; this conjecture proposes the corresponding locally varying bound. The source presents it as a belief and an open question, with no resolution supplied.

Sources & referencesView supporting material

Primary source

Marthe Bonamy, Michelle Delcourt, Richard Lang and Luke Postle, “Edge-colouring graphs with local list sizes”, arXiv:2007.14944 (2023).

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.