New examples of minimal non-strongly-perfect graphs

DOI10.1016/J.DISC.2021.112334MaRDI QIDQ2659246zbMATH OpenOpenAlexFDO

Authors Maria Chudnovsky, Cemil Dibek, Paul Seymour

Publication date 25 March 2021

Published in Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

forbidden induced subgraph characterizationnew minimal examplesstrongly perfect graphs

Mathematics Subject Classification ID

Perfect graphs (05C17) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Structural characterization of families of graphs (05C75)

Abstract: A graph is strongly perfect if every induced subgraph H has a stable set that meets every nonempty maximal clique of H. The characterization of strongly perfect graphs by a set of forbidden induced subgraphs is not known. Here we provide several new minimal non-strongly-perfect graphs.

Recommendations

• Some classes of strongly perfect graphs
• New results on minimal strongly imperfect graphs
• scientific article; zbMATH DE number 3926973
• scientific article; zbMATH DE number 3889565
• scientific article; zbMATH DE number 4041969

Cites work

• A class of strongly perfect graphs
• A decomposition for strongly perfect graphs
• scientific article; zbMATH DE number 3889565 (Why is no real title available?)
• scientific article; zbMATH DE number 3926973 (Why is no real title available?)
• New properties of perfectly orderable graphs and strongly perfect graphs
• New results on minimal strongly imperfect graphs
• Research problems
• Some classes of strongly perfect graphs
• Which claw-free graphs are strongly perfect?

Cited in

(8)

• Some classes of strongly perfect graphs
• Which claw-free graphs are strongly perfect?
• scientific article; zbMATH DE number 3889565 (Why is no real title available?)
• Structural properties of super strongly perfect graphs
• New results on minimal strongly imperfect graphs
• Super strongly perfect graphs
• SSP-cyclic structure of some circulant graphs
• Research problems

This page was built for publication: New examples of minimal non-strongly-perfect graphs

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