In 1980, Payan introduced equistable graphs as 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.
In 1993, McAvaney, Robertson, and DeTemple introduced general partition graphs as the intersection graphs of set systems over a finite ground set U such that every maximal stable set of the graph corresponds to a partition of U.
General partition graphs are exactly the graphs every edge of which is contained in a strong clique (that is, a clique intersecting all maximal stable sets).
In 1994, Mahadev, Peled, and Sun introduced strongly equistable graphs as graphs such that for every c ≤ 1 and every nonempty subset T of vertices that is not a maximal stable set, there exist positive vertex weights assigning weight 1 to every maximal stable set such that the total weight of T does not equal c. They 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 provide a combinatorial characterization of equistable graphs and imply the conjecture due to Mahadev, Peled, and Sun. An “intermediate” conjecture, posed by Miklavič and Milanič in 2011, states that every equistable graph has a strong clique.
The above conjectures have been verified for a number of graph classes.
In this talk we will present a construction, due to Milanič and Trotignon from 2017, of counterexamples to all three conjectures. The constructions are obtained within the class of complements of line graphs of triangle-free graphs and are based on connections with matchings and hamiltonicity. The same approach also leads to a separation between the classes of strongly equistable graphs and general partition graphs. We will also present several open questions.
Joint work with Nicolas Trotignon.
We are looking forward to meeting you at FAMNIT-MP1.
This Monday, January 10, 2022, from 10 am to 11 am.
Our Math Research Seminar will also be broadcasted via Zoom.
Join the Zoom Meeting Here.
See you there!
Everyone is welcome and encouraged to attend.