Pim van 't Hof

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ⁿ 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ⁿ 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ⁿ), yielding the fastest known algorithm for finding a maximum induced matching in a triangle-free graph.