Premium
Improved bounds for the chromatic index of graphs and multigraphs
Author(s) -
Hakimi S. Louis,
Schmeichel Edward F.
Publication year - 1999
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/(sici)1097-0118(199912)32:4<311::aid-jgt1>3.0.co;2-x
Subject(s) - multigraph , combinatorics , edge coloring , mathematics , multiplicity (mathematics) , graph , chromatic scale , simple graph , upper and lower bounds , simple (philosophy) , discrete mathematics , line graph , graph power , geometry , mathematical analysis , philosophy , epistemology
We show that coloring the edges of a multigraph G in a particular order often leads to improved upper bounds for the chromatic index χ′( G ). Applying this to simple graphs, we significantly generalize recent conditions based on the core of G 〈i.e., the subgraph of G induced by the vertices of degree Δ( G )〉, which insure that χ′( G ) = Δ( G ). Finally, we show that $\chi '(G) \leq \Delta (G) + \lceil \sqrt{\mu (G)}\rceil $ in any multigraph G in which every cycle of length larger than 2 contains a simple edge, where μ( G ) is the largest edge multiplicity in G . © 1999 John Wiley & Sons, Inc. J Graph Theory 32: 311–326, 1999