Forbidden induced pairs for perfectness and \(\omega\)-colourability of graphs

Maria Chudnovsky¹ ; Adam Kabela² ; Binlong Li³ ; Petr Vrána²

¹Princeton University
²University of West Bohemia
³Northwestern Polytechnical University

The electronic journal of combinatorics, Tome 29 (2022) no. 2

Résumé

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 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 $\chi$-boundedness and deciding $k$-colourability in polynomial time.

Détail

DOI : 10.37236/10708

Classification : 05C15, 05C17
Mots-clés : Ramsey's theorem, strong perfect graph theorem