Approximating the chromatic index of multigraphs

DOI10.1007/S10878-009-9232-YzbMATH Open1233.90268OpenAlexW2037535744WikidataQ56390627 ScholiaQ56390627MaRDI QIDQ630193FDOQ630193

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

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

zbMATH Keywords

multigraphedge coloringchromatic indexfractional chromatic index

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (21)

• On the total proper connection of graphs
• Chromatic index determined by fractional chromatic index
• A combined logarithmic bound on the chromatic index of multigraphs
• Goldberg's conjecture is true for random multigraphs
• Title not available (Why is that?)
• Edge coloring multigraphs without small dense subsets
• On the chromatic index and the cover index of a multigraph
• On characterizing Vizing's edge colouring bound
• On the chromatic index of multigraphs without large triangles
• A note concerning the chromatic index of multigraphs
• Efficiently list‐edge coloring multigraphs asymptotically optimally
• Achieving maximum chromatic index in multigraphs
• The maximum chromatic index of multigraphs with given \(\Delta \) and \(\mu \)
• Structural properties of edge-chromatic critical multigraphs
• Orientation‐based edge‐colorings and linear arboricity of multigraphs
• Improved bounds for the chromatic index of graphs and multigraphs
• Title not available (Why is that?)
• Title not available (Why is that?)
• On Vizing's bound for the chromatic index of a multigraph
• The chromatic index of multigraphs that are nearly full
• Graph edge coloring: a survey

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)