Forbidden induced pairs for perfectness and ω-colourability of graphs

Maria Chudnovsky, Adam Kabela, Binlong Li, Petr Vrána

Research output: Contribution to journalArticlepeer-review


We characterise the pairs of graphs {X, Y} such that all {X, Y}-free graphs (distinct from C5) are perfect. Similarly, we characterise pairs {X, Y} such that all {X, Y}-free graphs (distinct from C5) 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 n0, 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 {K1,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.

Original languageEnglish (US)
Article number#P2.21
JournalElectronic Journal of Combinatorics
Issue number2
StatePublished - 2022

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Geometry and Topology
  • Discrete Mathematics and Combinatorics
  • Computational Theory and Mathematics
  • Applied Mathematics


Dive into the research topics of 'Forbidden induced pairs for perfectness and ω-colourability of graphs'. Together they form a unique fingerprint.

Cite this