Maximal Induced Matchings in Triangle-Free Graphs

DOI10.1002/jgt.21994zbMath1350.05130arXiv1312.5180MaRDI QIDQ5891021

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

Publication date: 16 November 2016

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

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

zbMATH Keywords

extremal graphs; triangle-free graphs; polynomial delay; combinatorial bounds; maximal induced matchings

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

05C35: Extremal problems in graph theory

05C70: Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)

05C85: Graph algorithms (graph-theoretic aspects)