Forbidden induced pairs for perfectness and -colourability of graphs

DOI10.37236/10708zbMATH Open1487.05087arXiv2108.07071OpenAlexW3195878634MaRDI QIDQ2138579FDOQ2138579

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

Publication date: 12 May 2022

Published in: The Electronic Journal of Combinatorics (Search for Journal in Brave)

Abstract: 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.

Full work available at URL: https://arxiv.org/abs/2108.07071

File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

Recommendations

• On forbidden induced subgraphs for \(K_{1, 3}\)-free perfect graphs
• Forbidden induced subgraphs for perfectness of claw-free graphs of independence number at least 4
• ?-Perfect graphs
• Perfect coloring and linearly χ-boundP6-free graphs
• On the chromatic number of some \(P_5\)-free graphs

zbMATH Keywords

Ramsey's theoremstrong perfect graph theorem

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Perfect graphs (05C17)

Cites Work

• Graph theory
• Graph Theory and Probability
• Title not available (Why is that?)
• The ellipsoid method and its consequences in combinatorial optimization
• A characterization of perfect graphs
• Title not available (Why is that?)
• The strong perfect graph theorem
• Paw-free graphs
• Title not available (Why is that?)
• Title not available (Why is that?)
• On a property of the class of n-colorable graphs
• Claw-free graphs. VI: Colouring
• A survey on the computational complexity of coloring graphs with forbidden subgraphs
• The strong perfect graph conjecture: 40 years of attempts, and its resolution
• On the chromatic number of \(2 K_2\)-free graphs
• Polynomial \(\chi \)-binding functions and forbidden induced subgraphs: a survey
• Classes of perfect graphs
• On forbidden induced subgraphs for \(K_{1, 3}\)-free perfect graphs
• Coloring (gem, co‐gem)‐free graphs
• A survey of \(\chi\)-boundedness
• Graphs of bounded cliquewidth are polynomially \(\chi\)-bounded

Cited In (4)

• On forbidden induced subgraphs for \(K_{1, 3}\)-free perfect graphs
• Forbidden induced subgraphs for perfectness of claw-free graphs of independence number at least 4
• ?-Perfect graphs
• Title not available (Why is that?)

This page was built for publication: Forbidden induced pairs for perfectness and \(\omega\)-colourability of graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2138579)