Publication:5891021

DOI10.1007/978-3-319-12340-0_8zbMath1350.05130arXiv1312.5180OpenAlexW2887702900MaRDI QIDQ5891021

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

Publication date: 16 November 2016

Published in: Journal of Graph Theory, Graph-Theoretic Concepts in Computer Science (Search for Journal in Brave)

Abstract: 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^{n/5} approx 1.5849^n$ maximal induced matchings, and this bound is best possible. We prove that any $n$-vertex triangle-free graph has at most $3^{n/3} approx 1.4423^n$ maximal induced matchings, and this bound is attained by any 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.

Full work available at URL: https://arxiv.org/abs/1312.5180

zbMATH Keywords

extremal graphstriangle-free graphspolynomial delaycombinatorial boundsmaximal induced matchings

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Extremal problems in graph theory (05C35) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85)

Cites Work

• Unnamed Item
• Enumerating maximal independent sets with applications to graph colouring.
• On generating all maximal independent sets
• Induced matchings
• Strong edge-colouring and induced matchings
• A New Algorithm for Generating All the Maximal Independent Sets
• The Number of Maximal Independent Sets in Triangle-Free Graphs
• Maximum $r$-Regular Induced Subgraph Problem: Fast Exponential Algorithms and Combinatorial Bounds
• Maximal Induced Matchings in Triangle-Free Graphs
• On cliques in graphs

Related Items (9)

Maximal and maximum dissociation sets in general and triangle-free graphs ⋮ Almost Induced Matching: Linear Kernels and Parameterized Algorithms ⋮ Enumeration and maximum number of minimal connected vertex covers in graphs ⋮ Minimum number of maximal dissociation sets in trees ⋮ Unnamed Item ⋮ On the maximum number of maximum dissociation sets in trees with given dissociation number ⋮ Parameterized algorithms and kernels for almost induced matching ⋮ Maximal Induced Matchings in Triangle-Free Graphs ⋮ Maximal induced matchings in \(K_4\)-free and \(K_5\)-free graphs

This page was built for publication: Maximal Induced Matchings in Triangle-Free Graphs