Forbidden induced subgraphs of double-split graphs

DOI10.1137/100818121zbMATH Open1245.05054OpenAlexW3106397760MaRDI QIDQ2902883FDOQ2902883

Authors Boris Alexeev, Ilhee Kim, Alexandra Fradkin 

Publication date 22 August 2012

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

induced subgraphsperfect graphsgraph familiesdouble-split graphs

Mathematics Subject Classification ID

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

Abstract: In the course of proving the strong perfect graph theorem, Chudnovsky, Robertson, Seymour, and Thomas showed that every perfect graph either belongs to one of five basic classes or admits one of several decompositions. Four of the basic classes are closed under taking induced subgraphs (and have known forbidden subgraph characterizations), while the fifth one, consisting of double-split graphs, is not. A graph is doubled if it is an induced subgraph of a double-split graph. We find the forbidden induced subgraph characterization of doubled graphs; it contains 44 graphs.

Recommendations

• Forbidden induced subgraphs
• Forbidden induced subgraphs for star-free graphs
• Forbidden induced bipartite graphs
• On double bound graphs and forbidden subposets
• On double bound graphs and forbidden subposets
• Forbidden induced subgraph characterization of circle graphs within split graphs
• Forbidden subgraphs and forbidden substructures
• Forbidden induced subgraphs for line graphs
• Forbidden induced subgraphs for perfect matchings
• Splits with forbidden subgraphs

Cited In (8)

• Two forbidden induced subgraphs and well-quasi-ordering
• Forbidden graphs for classes of split-like graphs
• Coloring perfect graphs with no balanced skew-partitions
• Forbidden set of induced subgraphs for 2-connected supereulerian graphs
• Pairs of forbidden induced subgraphs for homogeneously traceable graphs
• On double bound graphs and forbidden subposets
• Star covers and star partitions of double-split graphs
• Fast recognition of doubled graphs

This page was built for publication: Forbidden induced subgraphs of double-split graphs

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