Forbidden induced subgraphs for perfectness of claw-free graphs of independence number at least 4

DOI10.1016/j.disc.2022.112837zbMath1487.05102arXiv2102.08783OpenAlexW3197272640MaRDI QIDQ2124634

Přemysl Holub, Ingo Schiermeyer, Zdeněk Ryjáček, Adam Kabela, Trung Duy Doan, Christoph Brause, Petr Vrána

Publication date: 11 April 2022

Published in: Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

perfect graphsforbidden induced subgraphsvertex colouring

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Perfect graphs (05C17) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

Cites Work

• Unnamed Item
• Claw-free graphs. VI: Colouring
• The strong perfect graph theorem
• Recognizing claw-free perfect graphs
• A strengthening of Ben Rebea's lemma
• Polynomial \(\chi \)-binding functions and forbidden induced subgraphs: a survey
• Vertex colouring and forbidden subgraphs -- a survey
• On forbidden induced subgraphs for \(K_{1, 3}\)-free perfect graphs
• A Survey on the Computational Complexity of Coloring Graphs with Forbidden Subgraphs
• The Ramsey number R(3, t) has order of magnitude t²/log t

This page was built for publication: Forbidden induced subgraphs for perfectness of claw-free graphs of independence number at least 4