Approximating the chromatic index of multigraphs

DOI10.1007/S10878-009-9232-YMaRDI QIDQ630193zbMATH OpenOpenAlexWikidataFDO

Authors Guantao Chen, Xingxing Yu, Wenan Zang

Publication date 17 March 2011

Published in Journal of Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s10878-009-9232-y

zbMATH Keywords

multigraphedge coloringchromatic indexfractional chromatic index

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Coloring of graphs and hypergraphs (05C15)

Recommendations

• Asymptotics of the chromatic index for multigraphs
• scientific article; zbMATH DE number 4122017
• The chromatic index of multigraphs that are nearly full
• Chromatic index determined by fractional chromatic index
• A note concerning the chromatic index of multigraphs

Cites work

• scientific article; zbMATH DE number 1560509 (Why is no real title available?)
• scientific article; zbMATH DE number 4195986 (Why is no real title available?)
• scientific article; zbMATH DE number 4195987 (Why is no real title available?)
• A Theorem on Coloring the Lines of a Network
• A better than “best possible” algorithm to edge color multigraphs
• A sublinear bound on the chromatic index of multigraphs
• An asymptotic approximation scheme for multigraph edge coloring
• Asymptotics of the chromatic index for multigraphs
• Colouring series-parallel graphs
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Edge-coloring of multigraphs: Recoloring technique
• Improving a family of approximation algorithms to edge color multigraphs
• Maximum matching and a polyhedron with 0,1-vertices
• On Multi-Colourings of Cubic Graphs, and Conjectures of Fulkerson and Tutte
• On edge-colorings of graphs.
• On the $1.1$ Edge-Coloring of Multigraphs
• On the chromatic index of multigraphs and a conjecture of Seymour (I)
• On the chromatic index of multigraphs without large triangles
• Regular Multigraphs of High Degree are 1-Factorizable
• The NP-Completeness of Edge-Coloring

Cited in

(24)

• Vizing's and Shannon's theorems for defective edge colouring
• On characterizing Vizing's edge colouring bound
• The maximum chromatic index of multigraphs with given \(\Delta \) and \(\mu \)
• Precoloring extension of Vizing's theorem for multigraphs
• scientific article; zbMATH DE number 1560509 (Why is no real title available?)
• On the total proper connection of graphs
• On Vizing's bound for the chromatic index of a multigraph
• Chromatic index determined by fractional chromatic index
• Orientation‐based edge‐colorings and linear arboricity of multigraphs
• A note concerning the chromatic index of multigraphs
• Graph edge coloring: a survey
• Improved bounds for the chromatic index of graphs and multigraphs
• On the chromatic index of multigraphs without large triangles
• scientific article; zbMATH DE number 3918395 (Why is no real title available?)
• On the chromatic index and the cover index of a multigraph
• scientific article; zbMATH DE number 4122017 (Why is no real title available?)
• Edge coloring multigraphs without small dense subsets
• Structural properties of edge-chromatic critical multigraphs
• The chromatic index of multigraphs that are nearly full
• Chromatic index, treewidth and maximum degree
• A combined logarithmic bound on the chromatic index of multigraphs
• Efficiently list‐edge coloring multigraphs asymptotically optimally
• Goldberg's conjecture is true for random multigraphs
• Achieving maximum chromatic index in multigraphs

This page was built for publication: Approximating the chromatic index of multigraphs

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