Forbidden induced pairs for perfectness and \(\omega\)-colourability of graphs (Q2138579): Difference between revisions

Summary: We characterise the pairs of graphs \(\{X, Y\}\) such that all \(\{X, Y\}\)-free graphs (distinct from \(C_5)\) are perfect. Similarly, we characterise pairs \(\{X, Y\}\) such that all \(\{X, Y\}\)-free graphs (distinct from \(C_5)\) are \(\omega\)-colourable (that is, their chromatic number is equal to their clique number). More generally, we show characterizations of pairs \(\{X, Y\}\) for perfectness and \(\omega\)-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_0\), and similar characterisations subject to each subset of these additional constraints. (The classes are non-hereditary and the characterisations for perfectness and \(\omega \)-colourability are different.) We build on recent results of \textit{C. Brause} et al. [Discrete Math. 342, No. 6, 1602--1608 (2019; Zbl 1414.05127); Discrete Appl. Math. 253, 14--24 (2019; Zbl 1401.05105)] 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 \(\chi\)-boundedness and deciding \(k\)-colourability in polynomial time.