Recent Results on Equimatchable Graphs

A graph G is called equimatchable (EQM for short) if every maximal matching of G has the same size. In the literature, there are several structural results on EQM graphs such as the characterizations of all 5-connected, planar EQM graphs, all cubic EQM graphs, EQM graphs with girth at least 5, factor-critical EQM graphs with vertex connectivity 1 and 2, etc. It is also known that EQM graphs can be recognized in polynomial time.

In this talk, we will consider several current research topics related to EQM graphs. Firstly, although the property of being EQM is not hereditary, we will exhibit an infinite family of forbidden subgraphs. Then we will consider EQM from a new point of view, namely EQM graphs such that the graph obtained by the removal of any edge is still EQM. We call these graphs edge-stable equimatchable (ESE for short) and give a full characterization of ESE graphs. We also introduce the opposite notion of edge-critical equimatchablegraphs (ECE for short) which are EQM graphs such that the removal of any edge harms the equimatchability. Lastly, we define some extensions of EQM graphs:

• Almost EQM graphs are the graphs for which the difference between the sizes of the smallest maximal matching and a maximum matching is 1.

• Greedy EQM graphs are a special case of weighted EQM graphs for which a greedy algorithm selecting a maximum weight edge in the remaining graph until a maximal matching is formed always yields a matching of the same total weight.

• EQM sets are sets of vertices V’ such that any maximal matching saturating all vertices of V’ has the same size.

We give recent results on these extensions and point out interesting research directions.

Short Bio:

Dr. Tınaz Ekim is Associate Professor at Boğaziçi Univeristy, Industrial Engineering Department. She holds B.S. degrees in Mathematics at University of Technology and Science of Lille (France, 1999) and inIndustrial Engineering at Galatasaray University (2001). She completed her MS and PhD in Operations Research at respectively Dauphine University (France) in 2002 and Swiss Federal Institute of Technology at Lausanne in 2006. Her research focus is on algorithmic and structural graph theory, combinatorial optimization and computational complexity.