On the 1.1 Edge-Coloring of Multigraphs

DOI10.1137/0403035MaRDI QIDQ3480065zbMATH OpenOpenAlexFDO

Authors Kenichi Kashiwagi, Takao Nishizeki

Publication date 1990

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/0403035

zbMATH Keywords

multigraph

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15)

Recommendations

• scientific article; zbMATH DE number 1560509
• The chromatic index of multigraphs that are nearly full
• scientific article; zbMATH DE number 3918395
• Edge-coloring of multigraphs
• A better than “best possible” algorithm to edge color multigraphs

Cited in

(33)

• Combinatorial algorithms for data migration to minimize average completion time
• Efficient algorithms for wavelength assignment on trees of rings
• On Vizing's bound for the chromatic index of a multigraph
• Graph edge coloring: a survey
• Chromatic index determined by fractional chromatic index
• Vizing's and Shannon's theorems for defective edge colouring
• A \(\frac{5}{2}\)-approximation algorithm for coloring rooted subtrees of a degree 3 tree
• On the fg-coloring of graphs
• Structural properties of edge-chromatic critical multigraphs
• Algorithms for data migration
• Path multicoloring with fewer colors in spiders and caterpillars
• An upper bound for the chromatic number of line graphs
• Edge-coloring of multigraphs
• From the quantum approximate optimization algorithm to a quantum alternating operator ansatz
• Edge colourings of embedded 1-graphs
• Multiply balanced edge colorings of multigraphs
• Improving a family of approximation algorithms to edge color multigraphs
• Vizing's coloring algorithm and the fan number
• On a theorem of Goldberg
• scientific article; zbMATH DE number 3889546 (Why is no real title available?)
• Bounding χ in terms of ω and Δ for quasi-line graphs
• scientific article; zbMATH DE number 3918395 (Why is no real title available?)
• A better than “best possible” algorithm to edge color multigraphs
• scientific article; zbMATH DE number 1560509 (Why is no real title available?)
• Densities, matchings, and fractional edge-colorings
• Experimental and Efficient Algorithms
• A brief history of edge-colorings -- with personal reminiscences
• The complexity of path coloring and call scheduling
• Efficiently list‐edge coloring multigraphs asymptotically optimally
• Approximating the chromatic index of multigraphs
• Proof of the Goldberg-Seymour conjecture on edge-colorings of multigraphs
• Inapproximability and approximability of minimal tree routing and coloring
• Graph edge colouring: Tashkinov trees and Goldberg's conjecture

This page was built for publication: On the $1.1$ Edge-Coloring of Multigraphs

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