The forbidden-matching avoidance conjecture

Let GG be a multigraph with maximum degree Δ(G)\Delta(G) and maximum multiplicity μ(G)\mu(G). A forbidden matching is a matching whose edges have been assigned arbitrary, not necessarily proper, colours from a palette. The forbidden-matching avoidance conjecture. Using the palette K=[Δ(G)+μ(G)]\mathcal{K}=[\Delta(G)+\mu(G)], any forbidden matching can be avoided by a proper edge-colouring of all of GG, meaning that the colouring disagrees with the assigned colour on every forbidden edge. This is a significant weakening of the edge-precolouring extension conjecture and is not implied by the List Colouring Conjecture; its proof was left open in the paper.

Sources & referencesView supporting material

Primary source

Katherine Edwards, António Girão, Jan van den Heuvel, Ross J. Kang, Gregory J. Puleo and Jean-Sébastien Sereni, “Extension from Precoloured Sets of Edges”, arXiv:1407.4339 (2018).

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.