Premium
Edge‐coloring of multigraphs: Recoloring technique
Author(s) -
Goldberg Mark K.
Publication year - 1984
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.3190080115
Subject(s) - multigraph , edge coloring , combinatorics , mathematics , vertex (graph theory) , graph , chromatic scale , brooks' theorem , enhanced data rates for gsm evolution , discrete mathematics , computer science , 1 planar graph , line graph , graph power , telecommunications
New upper and lower bounds for the chromatic index of a finite muitigraph are obtained. A complete description is given of multigraphs satisfying χ′ > 1/8(9ρ + 6) where χ′ and ρ denote the chromatic index and the maximum vertex degree of a multigraph. Some new and old conjectures are discussed.