Maximal induced matchings in triangle-free graphs

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

Research output: Contribution to journalArticleAcademicpeer-review

3 Citations (Scopus)

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 urn:x-wiley:03649024:media:jgt21994:jgt21994-math-0001 maximal induced matchings, and this bound is the best possible. We prove that every n‐vertex triangle‐free graph has at most urn:x-wiley:03649024:media:jgt21994:jgt21994-math-0002 maximal induced matchings; this bound is attained by every disjoint union of copies of the complete bipartite graph K3, 3. Our result implies that all maximal induced matchings in an n‐vertex triangle‐free graph can be listed in time urn:x-wiley:03649024:media:jgt21994:jgt21994-math-0003, yielding the fastest known algorithm for finding a maximum induced matching in a triangle‐free graph.
Original languageEnglish
Pages (from-to)231-250
JournalJournal of graph theory
Volume83
Issue number3
DOIs
Publication statusPublished - 2016
Externally publishedYes

Fingerprint Dive into the research topics of 'Maximal induced matchings in triangle-free graphs'. Together they form a unique fingerprint.

Cite this