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 language | English |
|---|---|
| Pages (from-to) | 231-250 |
| Journal | Journal of graph theory |
| Volume | 83 |
| Issue number | 3 |
| DOIs | |
| Publication status | Published - 2016 |
| Externally published | Yes |