Premium
A generalized construction of chromatic index critical graphs from bipartite graphs
Author(s) -
Plantholt Michael
Publication year - 1985
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.3190090309
Subject(s) - mathematics , bipartite graph , combinatorics , cograph , graph , discrete mathematics , indifference graph , extension (predicate logic) , edge coloring , 1 planar graph , chordal graph , line graph , graph power , computer science , programming language
We prove that any graph with maximum degree n which can be obtained by removing exactly 2n ‐ 1 edges from the join K 1 + K n, n is n ‐critical. This generalizes special constructions of critical graphs by S. Fiorini and H. P. Yap, and suggests a possible extension of another general construction due to Yap.
Accelerating Research
Robert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom
Address
John Eccles HouseRobert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom