A stable set in a graph is a set of pairwise non-adjacent vertices, and a stable set is maximal if it is not contained in any other stable set. Equistable graphs are graphs admitting positive weights on vertices such that a subset of vertices is a maximal stable set if and only if it is of total weight 1. General partition graphs are the intersection graphs of set systems over a finite ground set S such that every maximal stable set of the graph corresponds to a partition of S. It is known that general partition graphs are exactly the graphs such that every edge is contained in a strong clique (a clique is strong if it intersects all maximal stable sets).

No combinatorial characterization of equistable graphs is known. In 2009, Orlin proved that every general partition graph is equistable, and conjectured that the converse holds as well. Orlin’s conjecture has been verified for several graph classes, including line graphs, simplicial graphs, very  well-covered graps, chordal graphs, series-parallel graphs, AT-free graphs, EPT graphs, and certain graph products. Orlin’s conjecture, if true, would imply another conjecture on equistable graphs due to Mahadev, Peled, and Sun from 1994, stating that every equistable graph is strongly equistable. A conjecture that would follow from Orlin’s conjecture and would imply the conjecture by Mahadev, Peled, and Sun was posed in 2011 by Miklavič and Milanič in 2011, and states that every equistable graph has a strong clique.

In the talk, I will present an infinite family of counterexamples to Orlin’s conjecture. The family contains equistable graphs not having any strong cliques, and hence also disproves the conjecture by Miklavič and Milanič.

The results were obtained jointly with Stéphan Thomassé and Nicolas Trotignon, during a recent visit of the speaker at ENS Lyon.

DOWNLOAD SLIDES!