Intersection and Structured Graphs

(A post-workshop of the 2016 Haifa Graph Workshop)


 July 1-5, 2016


Sponsored by the Caesarea Rothschild Institute

upon invitation only

For further information, contact

Martin C. Golumbic <golumbic @>


  July 1-3, 2016Maale Hachamisha:  Research Discussions
  July 4, 2016    - Hebrew University, Dept. of Computer Science

Martin Milanic, University of Primorska, Koper, Slovenia 

Title Equistarable graphs and counterexamples to three conjectures on equistable graphs
Time 14:00 - Monday July 4, 2016
Room B220  Rothberg Building, Hebrew University, Givat Ram, Jerusalem




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 Miklavic and Milanic 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 graphs, 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 the above conjectures within the class of complements of line graphs of triangle-free graphs. 

Joint work with Nicolas Trotignon (ENS Lyon)