Maximal induced matchings in triangle-free graphs

Manu Basavaraju, Pinar Heggernes, Pim van 't Hof +2

An induced matching in a graph is a set of edges whose endpoints induce a $1$-regular subgraph. It is known that any $n$-vertex graph has at most $10^{n/5}\approx 1.5849^n$ maxima…