Premium
Maximal Induced Matchings in Triangle‐Free Graphs
Author(s) -
Basavaraju Manu,
Heggernes Pinar,
van ′t Hof Pim,
Saei Reza,
Villanger Yngve
Publication year - 2016
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.21994
Subject(s) - combinatorics , mathematics , factor critical graph , bipartite graph , induced subgraph , distance hereditary graph , vertex (graph theory) , discrete mathematics , disjoint sets , complete bipartite graph , matching (statistics) , line graph , graph , graph power , statistics
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 nmaximal induced matchings, and this bound is the best possible. We prove that every n ‐vertex triangle‐free graph has at most 3 n / 3 ≈ 1 . 4423 nmaximal 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.