Maximal Induced Matchings in Triangle-Free Graphs

Simple item page
dc.contributor.authorBasavaraju, M.
dc.contributor.authorHeggernes, P.
dc.contributor.authorvan 't'Hof, P.
dc.contributor.authorSaei, R.
dc.contributor.authorVillanger, Y.
dc.date.accessioned2026-02-05T09:32:58Z
dc.date.issued2016
dc.description.abstractAn 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 (Formula presented.) maximal induced matchings, and this bound is the best possible. We prove that every n-vertex triangle-free graph has at most (Formula presented.) maximal induced matchings; this bound is attained by every disjoint union of copies of the complete bipartite graph K<inf>3, 3</inf>. Our result implies that all maximal induced matchings in an n-vertex triangle-free graph can be listed in time (Formula presented.), yielding the fastest known algorithm for finding a maximum induced matching in a triangle-free graph. © 2015 Wiley Periodicals, Inc.
dc.identifier.citationJournal of Graph Theory, 2016, 83, 3, pp. 231-250
dc.identifier.issn3649024
dc.identifier.urihttps://doi.org/10.1002/jgt.21994
dc.identifier.urihttps://idr.nitk.ac.in/handle/123456789/25890
dc.publisherWiley-Liss Inc. info@wiley.com
dc.subjectCombinatorial bounds
dc.subjectExtremal graph
dc.subjectInduced matchings
dc.subjectPolynomial delays
dc.subjectTriangle-free graphs
dc.subjectGraph theory
dc.titleMaximal Induced Matchings in Triangle-Free Graphs

Files

Collections

Journal Articles