Extension from precoloured sets of edges
Edwards, Katherine; Girão, António; van den Heuvel, Jan
; Kang, Ross J.; Puleo, Gregory J.; and Sereni, Jean-Sébastien
(2018)
Extension from precoloured sets of edges
Electronic Journal of Combinatorics, 25 (3).
P3.1.
ISSN 1077-8926
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.
| Item Type | Article |
|---|---|
| Copyright holders | © 2018 The Authors © CC BY-ND 4.0 |
| Keywords | edge-colouring, precolouring extension, multigraphs, List colouring |
| Departments | Mathematics |
| Date Deposited | 04 Sep 2018 08:34 |
| Acceptance Date | 2018-05-16 |
| URI | https://researchonline.lse.ac.uk/id/eprint/90166 |
-
picture_as_pdf -
subject - Published Version
-
- Available under Creative Commons: Attribution-No Derivative Works 4.0
Download this file
Share this file
Downloads
ORCID: https://orcid.org/0000-0003-0897-9148