Intersection and Structured Graphs

Program: July 1-3, 2016 - Maale Hachamisha: Research Discussions

July 4, 2016 - Hebrew University, Dept. of Computer Science

Speaker: Martin Milanic, University of Primorska, Koper, Slovenia http://osebje.famnit.upr.si/~martin.milanic/

Title: Equistarable graphs and counterexamples to three conjectures on equistable graphs

Time: 14:00 - Monday July 4, 2016

Place: Room B220 Rothberg Building, Hebrew University, Givat Ram, Jerusalem

Abstract

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)