Title: Towards a combinatorial characterization of equistable graphs – partial results on a conjecture of Orlin

 

Abstract: Equistable graphs are graphs for which there exists a linear functional which characterizes the maximal stable sets of the graph. (A stable set is a set of pairwise non-adjacent vertices.) A conjecture due to Jim Orlin states that every equistable graph is a general partition graph (i.e., the intersection graph of a set system over a finite set S such that the maximal stable sets correspond precisely to the partitions of S using only sets from the family).

Orlin’s conjecture holds within the class of chordal graphs; if true in general, it would provide a combinatorial characterization of equistable graphs. In this talk, we will explain the known connections between general partition graphs, equistable graphs, and triangle graphs, and show some partial results on Orlin’s conjecture. In particular, we will present a complete characterization of equistable graphs decomposable with respect to the Cartesian or the tensor product.

SLIDES FROM THE LECTURE ARE AVAILABLE HERE: DOWNLOAD!