Extension from precoloured sets of edges

zbMATH Open1393.05115arXiv1407.4339MaRDI QIDQ1658745FDOQ1658745

Authors: Katherine Edwards, António Girão, Jan van den Heuvel, Ross J. Kang, Gregory J. Puleo, Jean-Sébastien Sereni 

Publication date: 15 August 2018

Published in: The Electronic Journal of Combinatorics (Search for Journal in Brave)

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 $Delta$. 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.

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

File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

Recommendations

• A precolouring extension of Vizing's theorem
• List-edge-colouring planar graphs with precoloured edges
• Edge precoloring extension of trees
• Extending an edge-coloring
• scientific article; zbMATH DE number 3875311

zbMATH Keywords

multigraphslist colouringedge-colouringprecolouring extension

Mathematics Subject Classification ID

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

Cites Work

• List edge and list total colourings of multigraphs
• Title not available (Why is that?)
• Every planar graph is 5-choosable
• Color-critical graphs on a fixed surface
• Graph colouring and the probabilistic method
• Title not available (Why is that?)
• The list chromatic index of a bipartite multigraph
• Asymptotics of the chromatic index for multigraphs
• Planar graphs of maximum degree seven are Class I
• Graph edge coloring. Vizing's theorem and Goldberg's conjecture
• Title not available (Why is that?)
• On Multi-Colourings of Cubic Graphs, and Conjectures of Fulkerson and Tutte
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• A Theorem on Coloring the Lines of a Network
• New Bounds on the List-Chromatic Index of the Complete Graph and Other Simple Graphs
• You can't paint yourself into a corner
• Planar graphs with maximum degree \(\Delta \geq 9\) are \((\Delta +1)\)-edge-choosable--a short proof
• A note on graph coloring extensions and list-colorings
• A note on \(K^-_{\Delta +1}\)-free precolouring with \(\Delta\) colours
• Precoloring Extensions of Brooks' Theorem
• Asymptotically good list-colorings
• Near-optimal list colorings
• Generalization of a theorem of Kotzig and a prescribed coloring of the edges of planar graphs
• Planar graphs with \(\Delta\geq 8\) are (\(\Delta+1\))-edge-choosable
• Graphs of degree 4 are 5-edge-choosable
• An application of matching theory of edge-colourings
• A short proof for a generalization of Vizing's theorem
• On decompositions of a multi-graph into spanning subgraphs
• Extending graph colorings using no extra colors
• On list edge-colorings of subcubic graphs
• Extending an edge-coloring
• On Vizing's bound for the chromatic index of a multigraph
• Kőnig's line coloring and Vizing's theorems for graphings

Cited In (15)

• Extending an edge-coloring
• Brooks' theorem with forbidden colors
• List-edge-colouring planar graphs with precoloured edges
• Avoiding and extending partial edge colorings of hypercubes
• Restricted extension of sparse partial edge colorings of hypercubes
• Embedding connected factorizations
• Extending partial edge colorings of iterated Cartesian products of cycles and paths
• Precoloring extension of Vizing's theorem for multigraphs
• List Coloring with a Bounded Palette
• A precolouring extension of Vizing's theorem
• Latin cubes of even order with forbidden entries
• Graph edge coloring: a survey
• Latin cubes with forbidden entries
• Edge precoloring extension of trees
• On the number of precolouring extensions

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)