Maximal induced matchings in triangle-free graphs

Original · EN

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