Extension from Precoloured Sets of Edges

Katherine Edwards (1) , António Girão (2) , Jan van den Heuvel (3) , Ross J. Kang (4) , Gregory J. Puleo (5) , Jean-Sébastien Sereni (6)

1 Department of Computer Science
2 DPMMS - Department of Pure Mathematics and Mathematical Statistics
3 LSE - Department Mathematics [London]
4 IMAPP - Applied Stochastics
5 CSL - Coordinated Science Laboratory
6 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? This question turns out to be related to the notorious List Colouring Conjecture and other classic notions of choosability.

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

Domaines: Combinatoire [math.CO]

Katherine Edwards, António Girão, Jan van den Heuvel, Ross J. Kang, Gregory J. Puleo, et al.. Extension from Precoloured Sets of Edges. The Electronic Journal of Combinatorics, 2018, ⟨10.37236/6303⟩. ⟨hal-01024843v3⟩