Maximal induced matchings in triangle-free graphs

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

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-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 10n/5≈1.5849n maximal induced matchings, and this bound is best possible. We prove that every n -vertex triangle-free graph has at most 3n/3≈1.4423n maximal induced matchings, and 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 O(1.4423n) , yielding the fastest known algorithm for finding a maximum induced matching in a triangle-free graph.
Original languageEnglish
Title of host publicationGraph-Theoretic Concepts in Computer Science - 40th International Workshop, WG 2014, Nouan-le-Fuzelier, France, June 25-27, 2014. Revised Selected Papers
EditorsDieter Kratsch, Ioan Todinca
PublisherSpringer Singapore
Pages93-104
Number of pages12
ISBN (Electronic)978-3-319-12340-0
ISBN (Print)978-3-319-12339-4
DOIs
Publication statusPublished - 2014
Externally publishedYes
Event40th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2014 - Nouan-le-Fuzelier, France
Duration: 25 Jun 201427 Jun 2014
Conference number: 40

Publication series

NameLecture Notes in Computer Science
PublisherSpringer
Volume8747

Conference

Conference40th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2014
Abbreviated titleWG
CountryFrance
CityNouan-le-Fuzelier
Period25/06/1427/06/14

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

Cite this