Conditions for β-perfectness
Judith Keijsper, Meike Tewes · Discussiones Mathematicae Graph Theory · 2002
A s-perfect graph is a simple graph G such that ?(G') = s(G') for every induced subgraph G' of G, where ?(G') is the chromatic number of G', and s(G') is defined as the maximum over all induced subgraphs H of G' of the minimum vertex degree in H plus 1 (i.e., d(H)+1). The vertices of a s-perfect graph G can be coloured with ?(G) colours in polynomial time (greedily). The main purpose of this paper is to give necessary and sufficient conditions, in terms of forbidden induced subgraphs, for a graph to be s-perfect. We give new sufficient conditions and make improvements to sufficient conditions previously given by others. We also mention a necessary condition which generalizes the fact that no s-perfect graph contains an even hole.