Premium
A generalization of Plantholt's theorem
Author(s) -
Hilton A. J. W.
Publication year - 1986
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.3190100410
Subject(s) - multigraph , combinatorics , mathematics , edge coloring , graph , chromatic scale , discrete mathematics , generalization , line graph , graph power , mathematical analysis
Let K 2 n +1 ( r )denote the complete graph K 2 n +1 with each edge replicated r times and let χ′( G ) denote the chromatic index of a multigraph G. A multigraph G is critical if χ′( G ) > χ′( G/e ) for each edge e of G. Let S be a set of sn – 1 edges of K 2 n +1 ( r ) . We show that, for 0 < s ≦ r , G/S is critical and that χ′ ( G/(S ∪{ e })) = 2 rn + r – s for all e ∈ E ( G/S ). Plantholt [ M . Plantholt, The chromatic index of graphs with a spanning star. J. Graph Theory 5 (1981) 5–13] proved this result in the case when r = 1.