Forbidden induced pairs for perfectness and -colourability of graphs

DOI10.37236/10708MaRDI QIDQ2138579zbMATH OpenOpenAlexFDO

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)

Copyright license Creative Commons Attribution 4.0 International

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

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

zbMATH Keywords

Ramsey's theoremstrong perfect graph theorem

Mathematics Subject Classification ID

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

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.

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

Cites work

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

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
• scientific article; zbMATH DE number 4063146 (Why is no real title available?)

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)