Premium
A generalization of simplicial elimination orderings
Author(s) -
Maffray Frédéric,
Porto Oscar,
Preissmann Myriam
Publication year - 1996
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(199610)23:2<203::aid-jgt11>3.0.co;2-h
Subject(s) - combinatorics , mathematics , strong perfect graph theorem , cograph , bipartite graph , split graph , perfect graph , discrete mathematics , chordal graph , graph coloring , conjecture , trivially perfect graph , indifference graph , pathwidth , graph , 1 planar graph , line graph
We consider the class of graphs where every induced subgraph possesses a vertex whose neighborhood has no P 4 and no 2 K 2 . We prove that Berge's Strong Perfect Graph Conjecture holds for such graphs. The class generalizes several well‐known families of perfect graphs, such as triangulated graphs and bipartite graphs. Testing membership in this class and computing the maximum clique size for a graph in this class is not hard, but finding an optimal coloring is NP‐hard. We give a polynomial‐time algorithm for optimally coloring the vertices of such a graph when it is perfect. © 1996 John Wiley & Sons, Inc.