## Maximal induced matchings in triangle-free graphs

*Manu Basavaraju, Pinar Heggernes, Pim van 't Hof, Reza Saei and Yngve Villanger*

*Journal of Graph Theory*, vol. 83, no. 3, pp. 231-250, 2016.

[__DOI__]
[__Preprint__]

A preliminary version of this paper will appear in the proceedings of WG 2014, the 40th International Workshop on Graph-Theoretic Concepts in Computer Science (held on June 25-27, 2014 in Le Domaine de Chalès, France), *Lecture Notes in Computer Science*, vol. 8747, pp. 93-104, 2014.

[__DOI__]

### Abstract:

An induced matching in a graph is a set of edges whose endpoints induce a 1-regular subgraph. It is known that every *n*-vertex graph has at most 10^{n/5} ≈ 1.5849^{n} maximal induced matchings, and this bound is best possible. We prove that every *n*-vertex triangle-free graph has at most 3^{n/3} ≈ 1.4423^{n} maximal induced matchings; this bound is attained by every 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.