Title: Two classes of <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="inline" id="d1e64" altimg="si72.svg"><mml:mi>β</mml:mi></mml:math>-perfect graphs that do not necessarily have simplicial extremes
Abstract: For a graph G, let β(G)=max{δ(G′)+1∣G′ is an induced subgraph of G}. This parameter is an upper bound on the chromatic number of a graph. A graph G is β-perfect if χ(G′)=β(G′) for all induced subgraphs G′ of G. A number of classes have been shown in literature to be β-perfect, but for the class of all β-perfect graphs, the complexity of their recognition and characterization in terms of forbidden induced subgraphs remain open. It is known that minimally β-imperfect graphs cannot have a simplicial extreme, i.e. a vertex whose neighborhood is a clique or of size 2. β-perfection of all the known β-perfect classes of graphs was shown through the existence of simplicial extremes. In this paper we study two classes of β-perfect graphs that do not necessarily have this property. Firstly, we prove that (even hole, twin wheel, cap)-free graphs are β-perfect. This class properly contains chordal graphs, and is the only known generalization of chordal graphs that is shown to be β-perfect. Secondly, we give a complete structural characterization of β-perfect hyperholes (graphs obtained from a hole by a sequence of clique substitutions), which we then use to give a linear-time algorithm to recognize whether a hyperhole is β-perfect. We also obtain a complete list of minimally β-imperfect hyperholes.