Premium
On critically perfect graphs
Author(s) -
Wagler Annegret
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<394::aid-jgt7>3.0.co;2-z
Subject(s) - mathematics , combinatorics , trivially perfect graph , cograph , indifference graph , discrete mathematics , strong perfect graph theorem , pathwidth , line graph , graph
A perfect graph is critical, if the deletion of any edge results in an imperfect graph. We give examples of such graphs and prove some basic properties. We relate critically perfect graphs to well‐known classes of perfect graphs, investigate the structure of the class of critically perfect graphs, and study operations preserving critical perfectness. © 1999 John Wiley & Sons, Inc. J Graph Theory 32: 394–404, 1999