Abstract: 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.
Recommendations
Cites work
- scientific article; zbMATH DE number 446487 (Why is no real title available?)
- scientific article; zbMATH DE number 3735847 (Why is no real title available?)
- scientific article; zbMATH DE number 3737686 (Why is no real title available?)
- scientific article; zbMATH DE number 1523257 (Why is no real title available?)
- scientific article; zbMATH DE number 3273761 (Why is no real title available?)
- scientific article; zbMATH DE number 3195967 (Why is no real title available?)
- A Theorem on Coloring the Lines of a Network
- A note on \(K^-_{\Delta +1}\)-free precolouring with \(\Delta\) colours
- A note on graph coloring extensions and list-colorings
- A short proof for a generalization of Vizing's theorem
- An application of matching theory of edge-colourings
- Asymptotically good list-colorings
- Asymptotics of the chromatic index for multigraphs
- Color-critical graphs on a fixed surface
- Every planar graph is 5-choosable
- Extending an edge-coloring
- Extending graph colorings using no extra colors
- Generalization of a theorem of Kotzig and a prescribed coloring of the edges of planar graphs
- Graph colouring and the probabilistic method
- Graph edge coloring. Vizing's theorem and Goldberg's conjecture
- Graphs of degree 4 are 5-edge-choosable
- Kőnig's line coloring and Vizing's theorems for graphings
- List edge and list total colourings of multigraphs
- Near-optimal list colorings
- New Bounds on the List-Chromatic Index of the Complete Graph and Other Simple Graphs
- On Multi-Colourings of Cubic Graphs, and Conjectures of Fulkerson and Tutte
- On Vizing's bound for the chromatic index of a multigraph
- On decompositions of a multi-graph into spanning subgraphs
- On list edge-colorings of subcubic graphs
- Planar graphs of maximum degree seven are Class I
- Planar graphs with \(\Delta\geq 8\) are (\(\Delta+1\))-edge-choosable
- Planar graphs with maximum degree \(\Delta \geq 9\) are \((\Delta +1)\)-edge-choosable--a short proof
- Precoloring Extensions of Brooks' Theorem
- The list chromatic index of a bipartite multigraph
- You can't paint yourself into a corner
Cited in
(15)- Avoiding and extending partial edge colorings of hypercubes
- On the number of precolouring extensions
- Precoloring extension of Vizing's theorem for multigraphs
- List Coloring with a Bounded Palette
- Graph edge coloring: a survey
- Extending partial edge colorings of iterated Cartesian products of cycles and paths
- A precolouring extension of Vizing's theorem
- Brooks' theorem with forbidden colors
- List-edge-colouring planar graphs with precoloured edges
- Latin cubes of even order with forbidden entries
- Latin cubes with forbidden entries
- Edge precoloring extension of trees
- Extending an edge-coloring
- Restricted extension of sparse partial edge colorings of hypercubes
- Embedding connected factorizations
This page was built for publication: Extension from precoloured sets of edges
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1658745)
