Description
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. Strongly equistable graphs are graphs such that for every c <= 1 and every non-empty subset T of vertices that is not a maximal stable set, there exist positive vertex weights such that every maximal stable set is of total weight 1 and the total weight of T does not equal c. 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 said to be strong if it intersects all maximal stable sets).
No combinatorial characterization of equistable graphs is known. In 1994, Mahadev-Peled, and Sun proved that every strongly equistable graph is equistable, and conjectured that the converse holds as well. In 2009, Orlin proved that every general partition graph is equistable, and conjectured that the converse holds as well. Orlin's conjecture, if true, would imply the conjecture due to Mahadev, Peled, and Sun. An "intermediate" conjecture, one that would follow from Orlin's conjecture and would imply the conjecture by Mahadev, Peled, and Sun, was posed by Miklavič and Milanič in 2011, and states that every equistable graph has a strong clique. The above conjectures have 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.
We introduce the notion of equistarable graphs, and based on it construct counterexamples to all three conjectures within the class of complements of line graphs of triangle-free graphs.
Joint work with Nicolas Trotignon.
Primary author
Dr
Martin Milanič
(University of Primorska)
Co-author
Prof.
Nicolas Trotignon
(ENS Lyon)
