Edge-coloring of multigraphs: Recoloring technique

DOI10.1002/JGT.3190080115MaRDI QIDQ3216672zbMATH OpenOpenAlexFDO

Authors Mark K. Goldberg

Publication date 1984

Published in Journal of Graph Theory (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1002/jgt.3190080115

zbMATH Keywords

chromatic indexedge-colouringslink-chain recolouringmultigraphs

Mathematics Subject Classification ID

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

Recommendations

• The chromatic index of multigraphs that are nearly full
• A note concerning the chromatic index of multigraphs
• scientific article; zbMATH DE number 3918395
• Edge-coloring of multigraphs
• A new method of proving theorems on chromatic index

Cites work

• A Theorem on Coloring the Lines of a Network
• Cybernetics
• Some remarks on the chromatic index of a graph

Cited in

(31)

• Achieving maximum chromatic index in multigraphs
• A theorem in edge colouring
• On Vizing's bound for the chromatic index of a multigraph
• On the chromatic index of multigraphs and a conjecture of Seymour (I)
• Applications of edge coloring of multigraphs to vertex coloring of graphs
• A sublinear bound on the chromatic index of multigraphs
• On Vizing's theorem, adjacency lemma and fan argument generalized to multigraphs
• Graph edge coloring: a survey
• Chromatic index determined by fractional chromatic index
• On the coequal values of total chromatic number and chromatic index
• Goldberg's conjecture is true for random multigraphs
• Structural properties of edge-chromatic critical multigraphs
• A new tool for proving Vizing's theorem
• Edge coloring multigraphs without small dense subsets
• Using the minimum maximum flow degree to approximate the flow coloring problem
• On a limit of the method of Tashkinov trees for edge-colouring
• Vizing's coloring algorithm and the fan number
• On a theorem of Goldberg
• Densities, matchings, and fractional edge-colorings
• Improved bounds for the chromatic index of graphs and multigraphs
• The edge-recoloring cost of monochromatic and properly edge-colored paths and cycles
• A combined logarithmic bound on the chromatic index of multigraphs
• Short fans and the 5/6 bound for line graphs
• A brief history of edge-colorings -- with personal reminiscences
• A note on Goldberg's conjecture on total chromatic numbers
• Total colorings-a survey
• Approximating the chromatic index of multigraphs
• Proof of the Goldberg-Seymour conjecture on edge-colorings of multigraphs
• The chromatic index of multigraphs that are nearly full
• An adjacency Lemma for critical multigraphs
• Graph edge colouring: Tashkinov trees and Goldberg's conjecture

This page was built for publication: Edge-coloring of multigraphs: Recoloring technique

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