Forbidden induced pairs for perfectness and ω-colourability of graphs

We characterise the pairs of graphs {X, Y} such that all {X, Y}-free graphs (distinct from C₅) are perfect. Similarly, we characterise pairs {X, Y} such that all {X, Y}-free graphs (distinct from C₅) are ω-colourable (that is, their chromatic number is equal to their clique number). More generally, we show characterizations of pairs {X, Y} for perfectness and ω-colourability of all connected {X, Y}-free graphs which are of independence at least 3, distinct from an odd cycle, and of order at least n₀, and similar characterisations subject to each subset of these ad-ditional constraints. (The classes are non-hereditary and the characterisations for perfectness and ω-colourability are different.) We build on recent results of Brause et al. on {K_1,3, Y}-free graphs, and we use Ramsey’s Theorem and the Strong Perfect Graph Theorem as main tools. We relate the present characterisations to known results on forbidden pairs for χ-boundedness and deciding k-colourability in polynomial time.