2021 | OriginalPaper | Buchkapitel
Subdivided Claws and the Clique-Stable Set Separation Property
verfasst von : Maria Chudnovsky, Paul Seymour
Erschienen in: 2019-20 MATRIX Annals
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Let $$ {\mathscr{C}} $$ C be a class of graphs closed under taking induced subgraphs. We say that $$ {\mathscr{C}} $$ C has the clique-stable set separation property if there exists $$ c \in {\mathbb{N}} $$ c ∈ N such that for every graph $$ G \in {\mathscr{C}} $$ G ∈ C there is a collection $$ {\mathscr{P}} $$ P of partitions (X, Y) of the vertex set of G with | $$ {\mathscr{P}}$$ P | ≤ |V(G)|c and with the following property: if K is a clique of G, and S is a stable set of G, and K ∩ S = $$ \emptyset$$ ∅ , then there is (X, Y) ∊ $$ {\mathscr{P}}$$ P with K ⊆ X and S ⊆ Y. In 1991 M. Yannakakis conjectured that the class of all graphs has the clique-stable set separation property, but this conjecture was disproved by M. Göös in 2014. Therefore it is now of interest to understand for which classes of graphs such a constant c exists. In this paper we define two infinite families $$ {\mathscr{S}}, {\mathscr{K}}$$ S , K of graphs and show that for every S ∊ $$ {\mathscr{S}}$$ S and K ∊ $${\mathscr{K}}$$ K , the class of graphs with no induced subgraph isomorphic to S or K has the clique-stable set separation property.