Maximal induced matchings in triangle-free graphs

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

doi:10.1007/978-3-319-12340-0_8

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 proceeding › Conference contribution › Academic › peer-review

4 Citations (Scopus)

15 Downloads (Pure)

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 language	English
Title of host publication	Graph-Theoretic Concepts in Computer Science - 40th International Workshop, WG 2014, Nouan-le-Fuzelier, France, June 25-27, 2014. Revised Selected Papers
Editors	Dieter Kratsch, Ioan Todinca
Publisher	Springer
Pages	93-104
Number of pages	12
ISBN (Electronic)	978-3-319-12340-0
ISBN (Print)	978-3-319-12339-4
DOIs	https://doi.org/10.1007/978-3-319-12340-0_8
Publication status	Published - 2014
Externally published	Yes
Event	40th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2014 - Nouan-le-Fuzelier, France Duration: 25 Jun 2014 → 27 Jun 2014 Conference number: 40

Publication series

Name	Lecture Notes in Computer Science
Publisher	Springer
Volume	8747

Conference

Conference	40th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2014
Abbreviated title	WG
Country/Territory	France
City	Nouan-le-Fuzelier
Period	25/06/14 → 27/06/14

Access to Document

10.1007/978-3-319-12340-0_8

Basavaraju-2014-Maximal-induced-matchings-in-triangSubmitted version, 196 KB

Cite this

Basavaraju, M., Heggernes, P., van 't Hof, P., Saei, R., & Villanger, Y. (2014). Maximal induced matchings in triangle-free graphs. In D. Kratsch, & I. Todinca (Eds.), Graph-Theoretic Concepts in Computer Science - 40th International Workshop, WG 2014, Nouan-le-Fuzelier, France, June 25-27, 2014. Revised Selected Papers (pp. 93-104). (Lecture Notes in Computer Science; Vol. 8747). Springer. https://doi.org/10.1007/978-3-319-12340-0_8

Basavaraju, Manu ; Heggernes, Pinar ; van 't Hof, Pim et al. / Maximal induced matchings in triangle-free graphs. Graph-Theoretic Concepts in Computer Science - 40th International Workshop, WG 2014, Nouan-le-Fuzelier, France, June 25-27, 2014. Revised Selected Papers. editor / Dieter Kratsch ; Ioan Todinca. Springer, 2014. pp. 93-104 (Lecture Notes in Computer Science).

@inproceedings{5ea9b417ee064d979e33c6be613fc7dd,

title = "Maximal induced matchings in triangle-free graphs",

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.",

author = "Manu Basavaraju and Pinar Heggernes and {van 't Hof}, Pim and Reza Saei and Yngve Villanger",

year = "2014",

doi = "10.1007/978-3-319-12340-0_8",

language = "English",

isbn = "978-3-319-12339-4",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "93--104",

editor = "Dieter Kratsch and Ioan Todinca",

booktitle = "Graph-Theoretic Concepts in Computer Science - 40th International Workshop, WG 2014, Nouan-le-Fuzelier, France, June 25-27, 2014. Revised Selected Papers",

address = "Germany",

note = "40th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2014, WG ; Conference date: 25-06-2014 Through 27-06-2014",

}

Basavaraju, M, Heggernes, P, van 't Hof, P, Saei, R & Villanger, Y 2014, Maximal induced matchings in triangle-free graphs. in D Kratsch & I Todinca (eds), Graph-Theoretic Concepts in Computer Science - 40th International Workshop, WG 2014, Nouan-le-Fuzelier, France, June 25-27, 2014. Revised Selected Papers. Lecture Notes in Computer Science, vol. 8747, Springer, pp. 93-104, 40th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2014, Nouan-le-Fuzelier, France, 25/06/14. https://doi.org/10.1007/978-3-319-12340-0_8

Maximal induced matchings in triangle-free graphs. / Basavaraju, Manu; Heggernes, Pinar; van 't Hof, Pim et al.
Graph-Theoretic Concepts in Computer Science - 40th International Workshop, WG 2014, Nouan-le-Fuzelier, France, June 25-27, 2014. Revised Selected Papers. ed. / Dieter Kratsch; Ioan Todinca. Springer, 2014. p. 93-104 (Lecture Notes in Computer Science; Vol. 8747).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

T1 - Maximal induced matchings in triangle-free graphs

AU - Basavaraju, Manu

AU - Heggernes, Pinar

AU - van 't Hof, Pim

AU - Saei, Reza

AU - Villanger, Yngve

N1 - Conference code: 40

PY - 2014

Y1 - 2014

N2 - 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.

AB - 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.

U2 - 10.1007/978-3-319-12340-0_8

DO - 10.1007/978-3-319-12340-0_8

M3 - Conference contribution

SN - 978-3-319-12339-4

T3 - Lecture Notes in Computer Science

SP - 93

EP - 104

BT - Graph-Theoretic Concepts in Computer Science - 40th International Workshop, WG 2014, Nouan-le-Fuzelier, France, June 25-27, 2014. Revised Selected Papers

A2 - Kratsch, Dieter

A2 - Todinca, Ioan

PB - Springer

T2 - 40th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2014

Y2 - 25 June 2014 through 27 June 2014

ER -

Basavaraju M, Heggernes P, van 't Hof P, Saei R, Villanger Y. Maximal induced matchings in triangle-free graphs. In Kratsch D, Todinca I, editors, Graph-Theoretic Concepts in Computer Science - 40th International Workshop, WG 2014, Nouan-le-Fuzelier, France, June 25-27, 2014. Revised Selected Papers. Springer. 2014. p. 93-104. (Lecture Notes in Computer Science). doi: 10.1007/978-3-319-12340-0_8

Maximal induced matchings in triangle-free graphs

Abstract

Publication series

Conference

Access to Document

Fingerprint

Cite this