Maximal induced matchings in triangle-free graphs

Abstract

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$ maximal induced matchings, and this bound is best possible. We prove that any $n$-vertex triangle-free graph has at most $3^{n/3}\approx 1.4423^n$ maximal induced matchings, and this bound is attained by any disjoint union of copies of the complete bipartite graph $K_{3,3}$. Our result implies that all maximal induced matchings in an $n$-vertex triangle-free graph can be listed in time $O(1.4423^n)$, yielding the fastest known algorithm for finding a maximum induced matching in a triangle-free graph.

17 pages