Maximal Induced Matchings in Triangle-Free Graphs

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

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

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 graphstriangle-free graphspolynomial delaycombinatorial boundsmaximal induced matchings

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Extremal problems in graph theory (05C35) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (8)

Maximal and maximum dissociation sets in general and triangle-free graphs ⋮ Almost Induced Matching: Linear Kernels and Parameterized Algorithms ⋮ Enumeration and maximum number of minimal connected vertex covers in graphs ⋮ Minimum number of maximal dissociation sets in trees ⋮ Unnamed Item ⋮ On the maximum number of maximum dissociation sets in trees with given dissociation number ⋮ Parameterized algorithms and kernels for almost induced matching ⋮ Maximal Induced Matchings in Triangle-Free Graphs

Cites Work

• Unnamed Item
• Enumerating maximal independent sets with applications to graph colouring.
• On generating all maximal independent sets
• Induced matchings
• Strong edge-colouring and induced matchings
• A New Algorithm for Generating All the Maximal Independent Sets
• The Number of Maximal Independent Sets in Triangle-Free Graphs
• Maximum $r$-Regular Induced Subgraph Problem: Fast Exponential Algorithms and Combinatorial Bounds
• Maximal Induced Matchings in Triangle-Free Graphs
• On cliques in graphs

This page was built for publication: Maximal Induced Matchings in Triangle-Free Graphs