Extension from Precoloured Sets of Edges

Katherine Edwards (1) , Jan van den Heuvel (2) , Ross J. Kang (3) , Jean-Sébastien Sereni (4)

1 Department of Computer Science
2 LSE - Department Mathematics [London]
3 IMAPP - Applied Stochastics
4 ORPAILLEUR - Knowledge representation, reasonning

We consider precolouring extension problems for proper edge-colourings of graphs and multigraphs, in an attempt to prove stronger versions of Vizing's and Shannon's bounds on the chromatic index of (multi)graphs in terms of their maximum degree Δ. We are especially interested in the following question: when is it possible to extend a precoloured matching to a colouring of all edges of a (multi)graph? For simple graphs, we conjecture that it is guaranteed as long as the predefined set of available colours has cardinality Δ+1. This turns out to be related to the notorious list colouring conjecture and other classic notions of choosability.

Mots clés: edge-colouring; precolouring; mutligraph; colouring extension

Domaines: Combinatoire [math.CO]

Katherine Edwards, Jan van den Heuvel, Ross J. Kang, Jean-Sébastien Sereni. Extension from Precoloured Sets of Edges. [Research Report] Loria & Inria Grand Est. 2014. ⟨hal-01024843v1⟩