Premium
Regular Multigraphs of High Degree are 1‐Factorizable
Author(s) -
Plantholt Michael J.,
Tipnis Shailesh K.
Publication year - 1991
Publication title -
journal of the london mathematical society
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.441
H-Index - 62
eISSN - 1469-7750
pISSN - 0024-6107
DOI - 10.1112/jlms/s2-44.3.393
Subject(s) - degree (music) , mathematics , graph , simple (philosophy) , combinatorics , simple graph , multigraph , edge coloring , order (exchange) , chromatic scale , discrete mathematics , line graph , physics , graph power , philosophy , economics , epistemology , finance , acoustics
Chetwynd and Hilton showed that any regular simple graph with even order n and maximum degree at least ⅚ n has chromatic index equal to its maximum degree. We show how to extend this result to general multigraphs, including those of odd order. This also verifies a special case of conjectures by Goldberg and Seymour.