Strongly perfect claw‐free graphs—A short proof

Redirect to:

• Strongly perfect claw‐free graphs—A short proof

DOI10.1002/JGT.22659MaRDI QIDQ6080850zbMATH OpenOpenAlexFDO

Authors Maria Chudnovsky, Cemil Dibek

Publication date 4 October 2023

Published in Journal of Graph Theory (Search for Journal in Brave)

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

zbMATH Keywords

claw-free graphsinduced subgraphsperfect graphsstrongly perfect graphs

Mathematics Subject Classification ID

Perfect graphs (05C17)

Abstract: A graph is strongly perfect if every induced subgraph H has a stable set that meets every maximal clique of H. A graph is claw-free if no vertex has three pairwise non-adjacent neighbors. The characterization of claw-free graphs that are strongly perfect by a set of forbidden induced subgraphs was conjectured by Ravindra in 1990 and was proved by Wang in 2006. Here we give a shorter proof of this characterization.

Recommendations

• The structure of claw-free perfect graphs
• Strong cliques in claw-free graphs
• On claw-free t-perfect graphs
• Claw-free graphs with strongly perfect complements. Fractional and integral version. I: Basic graphs
• A description of claw-free perfect graphs
• A characterization of claw-free \(b\)-perfect graphs
• On the choosability of claw-free perfect graphs
• \(t\)-perfection is always strong for claw-free graphs
• Clique-perfectness of claw-free planar graphs
• Almost claw‐free graphs

Cites work

• A description of claw-free perfect graphs
• Claw-free graphs. III: Circular interval graphs
• Difference graphs
• scientific article; zbMATH DE number 3889565 (Why is no real title available?)
• scientific article; zbMATH DE number 3891425 (Why is no real title available?)
• scientific article; zbMATH DE number 3926973 (Why is no real title available?)
• Perfect Elimination and Chordal Bipartite Graphs
• Recognizing claw-free perfect graphs
• Research problems
• Some classes of strongly perfect graphs
• The strong perfect graph theorem
• Which claw-free graphs are perfectly orderable?
• Which claw-free graphs are strongly perfect?

Cited in

(5)

• On the choice number of claw-free perfect graphs
• Partial characterizations of clique-perfect graphs I: Subclasses of claw-free graphs
• Claw-free graphs with strongly perfect complements. Fractional and integral version. II: Nontrivial strip-structures
• On claw-free t-perfect graphs
• Homogeneous sets in graphs and a chromatic multisymmetric function

This page was built for publication: Strongly perfect claw‐free graphs—A short proof

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