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.