A precolouring extension of Vizing's theorem

DOI10.1002/JGT.22451MaRDI QIDQ5207466zbMATH OpenOpenAlexWikidataFDO

Authors António Girão, Ross J. Kang

Publication date 30 December 2019

Published in Journal of Graph Theory (Search for Journal in Brave)

Copyright license Creative Commons Attribution-NonCommercial 4.0 International

Full work available at URL https://arxiv.org/abs/1611.09002

zbMATH Keywords

edge-coloringprecolouring extensionVizing's theorem

Mathematics Subject Classification ID

Vertex degrees (05C07) Distance in graphs (05C12) Coloring of graphs and hypergraphs (05C15) Extremal problems in graph theory (05C35)

Abstract: Fix a palette $mathcalK$ of $Delta+1$ colours, a graph with maximum degree $Delta$, and a subset $M$ of the edge set with minimum distance between edges at least $9$. If the edges of $M$ are arbitrarily precoloured from $mathcalK$, then there is guaranteed to be a proper edge-colouring using only colours from $mathcalK$ that extends the precolouring on $M$ to the entire graph. This result is a first general precolouring extension form of Vizing's theorem, and it proves a conjecture of Albertson and Moore under a slightly stronger distance requirement. We also show that the condition on the distance can be lowered to $5$ when the graph contains no cycle of length $5$.

Recommendations

• Extension from precoloured sets of edges
• Precoloring Extensions of Brooks' Theorem
• A note on \(K^-_{\Delta +1}\)-free precolouring with \(\Delta\) colours
• List-edge-colouring planar graphs with precoloured edges
• Extending graph colorings

Cited in

(11)

• On the number of precolouring extensions
• List-edge-colouring planar graphs with precoloured edges
• Extension from precoloured sets of edges
• Restricted extension of sparse partial edge colorings of hypercubes
• A note on \(K^-_{\Delta +1}\)-free precolouring with \(\Delta\) colours
• On Vizing's edge colouring question
• Edge precoloring extension of trees
• Extending partial edge colorings of iterated Cartesian products of cycles and paths
• Precoloring extension of Vizing's theorem for multigraphs
• Extending partial edge colorings of Cartesian products of graphs
• Edge precoloring extension of trees. II

This page was built for publication: A precolouring extension of Vizing's theorem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5207466)