Abstract

The equistable graphs were introduced by Payan in 1980 as a generalization of threshold graphs. A graph G is called equistable if it has positive vertex weights such that a subset of vertices of G has total weight 1 if and only if it is a maximal stable set in G (maximal with respect to inclusion). Recognizing an equistable graph can be done in exponential time by using linear programming, but this problem is not even known to be in NP. A necessary condition for equistability is that for each induced P_4 (a path on 4 vertices), each maximal stable set containing the end vertices must contain a common neighbor of the two middle vertices. Checking this property for a given induced P_4 is co-NP complete, and probably checking the necessary condition itself is hard. There is a subclass of the equistable graphs called strongly equistable graphs, containing in particular all co-graphs (graphs without induced P_4). It is conjectured that each equistable graph is in fact strongly equistable. A sufficient condition for strong equistability of G is that the simplicial cliques of G (induced by a simplicial vertex and all its neighbors) cover all the edges of G, and this condition is easy to check. It turns out that for chordal graphs and for series-parallel graphs, equistability and strong equistability are indeed equivalent. For these graph classes, structural characterizations of equistability using the sufficient condition are known. For perfect graphs too, equistability is equivalent to strong equistablilty, but no structural characterization is known.
The talk will survey these results.

Dr. Uri N. Peled is a professor in the Department of Mathematics, Statistics, and Computer Science at the University of Illinois at Chicago. He works in graph theory, combinatorics, and combinatorial optimization, particularly in problems involving threshold graphs and graphical degree sequences, classes of chordal graphs, matroids, list colorings, and facets of knapsack polytopes. His book with N. V. R. Mahadev titled Threshold Graphs and Related Topics was published in the Annals of Discrete Mathematics in 1995. He studied at the Hebrew University, Weizmann Institute of Science, The Technion, and the University of Waterloo, where he received his PhD. He was a post doctoral fellow at the University of Toronto and an assistant professor at Columbia University before coming to Chicago.