Approximating the chromatic index of multigraphs

DOI10.1007/s10878-009-9232-yzbMath1233.90268OpenAlexW2037535744WikidataQ56390627 ScholiaQ56390627MaRDI QIDQ630193

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)

Related Items (10)

A Combined Logarithmic Bound on the Chromatic Index of Multigraphs ⋮ Efficiently list‐edge coloring multigraphs asymptotically optimally ⋮ Orientation‐based edge‐colorings and linear arboricity of multigraphs ⋮ Graph edge coloring: a survey ⋮ Chromatic index determined by fractional chromatic index ⋮ On the total proper connection of graphs ⋮ Edge coloring multigraphs without small dense subsets ⋮ Goldberg's conjecture is true for random multigraphs ⋮ On characterizing Vizing's edge colouring bound ⋮ Structural properties of edge-chromatic critical multigraphs

Cites Work

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

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