Maximal Induced Matchings in Triangle‐Free Graphs |
| |
| Authors: | Manu Basavaraju Pinar Heggernes Pim van ′t Hof Reza Saei Yngve Villanger |
| |
| Institution: | 1. DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING, NATIONAL INSTITUTE OF TECHNOLOGY KARNATAKA, INDIA;2. DEPARTMENT OF INFORMATICS, UNIVERSITY OF BERGEN, BERGEN, NORWAY;3. SCHOOL OF BUILT ENVIRONMENT, ROTTERDAM UNIVERSITY OF APPLIED SCIENCES, ROTTERDAM, THE NETHERLANDS |
| |
| 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  maximal induced matchings, and this bound is the best possible. We prove that every n‐vertex triangle‐free graph has at most  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  , yielding the fastest known algorithm for finding a maximum induced matching in a triangle‐free graph. |
| |
| Keywords: | maximal induced matchings triangle‐free graphs polynomial delay combinatorial bounds extremal graphs |
|
|
