Clique-Stable Set Separation in Perfect Graphs with no Balanced Skew-Partitions

Aurélie Lagoutte (1) , Théophile Trunck (1)

1 MC2 - Modèles de calcul, Complexité, Combinatoire

Inspired by a question of Yannakakis on the Vertex Packing polytope of perfect graphs, we study the Clique-Stable Set separation in a non-hereditary subclass of perfect graphs. A cut (B, W) of G (a bipartition of V (G)) separates a clique K and a stable set S if $K ⊆ B$ and $S ⊆ W$. A Clique-Stable Set separator is a family of cuts such that for every clique K, and for every stable set S disjoint from K, there exists a cut in the family that separates K and S. Given a class of graphs, the question is to know whether every graph of the class admits a Clique-Stable Set separator containing only polynomially many cuts. It was recently proved to be false for the class of all graphs (Göös 2015), but it remains open for perfect graphs, which was Yannakakis' original question. Here we investigate this problem on perfect graphs with no balanced skew-partition; the balanced skew-partition was introduced in the decomposition theorem of Berge graphs which led to the celebrated proof of the Strong Perfect Graph Theorem. Recently, Chudnovsky, Trotignon, Trunck and Vuškovi´Vuškovi´c proved that forbidding this unfriendly decomposition permits to recursively decompose Berge graphs (more precisely, Berge trigraphs) using 2-join and complement 2-join until reaching a " basic " graph, and in this way, they found an efficient combinatorial algorithm to color those graphs. We apply their decomposition result to prove that perfect graphs with no balanced skew-partition admit a quadratic-size Clique-Stable Set separator, by taking advantage of the good behavior of 2-join with respect to this property. We then generalize this result and prove that the Strong Erd˝ os-Hajnal property holds in this class, which means that every such graph has a linear-size biclique or complement biclique. This is remarkable since the property does not hold for all perfect graphs (Fox 2006), and this is motivated here by the following statement: when the Strong Erdös-Hajnal property holds in a hereditary class of graphs, then both the Erdöos-Hajnal property and the polynomial Clique-Stable Set separation hold. Finally, we define the generalized k-join and generalize both our results on classes of graphs admitting such a decomposition.

Mots clés: Clique-Stable Set separation; perfect graph; trigraph; 2-join

Domaines: Mathématique discrète [cs.DM]; Combinatoire [math.CO]

Aurélie Lagoutte, Théophile Trunck. Clique-Stable Set Separation in Perfect Graphs with no Balanced Skew-Partitions. Discrete Mathematics, 2016, 339, pp.1809 - 1825. ⟨10.1016/j.disc.2016.02.005⟩. ⟨hal-01508655⟩