Maximal induced matchings in \(K_4\)-free and \(K_5\)-free graphs

DOI10.1016/j.dam.2024.09.027MaRDI QIDQ6633556

Erik Jan van Leeuwen, Manu Basavaraju, Reza Saei

Publication date: 6 November 2024

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

zbMATH Keywords

\(K_4\)-free graphsmaximal induced matchings\(K_5\)-free graphs

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Cites Work

• Unnamed Item
• Enumerating maximal independent sets with applications to graph colouring.
• On generating all maximal independent sets
• Induced matchings
• The maximum number of triangles in a \(K_4\)-free graph
• On the maximum number of independent cycles in a graph
• Maximal independent sets in graphs with at mostr cycles
• The Number of Maximal Independent Sets in a Tree
• Lower bounds on the number of triangles in a graph
• A New Algorithm for Generating All the Maximal Independent Sets
• The Number of Maximal Independent Sets in Triangle-Free Graphs
• Induced Matchings in Subcubic Planar Graphs
• Maximum $r$-Regular Induced Subgraph Problem: Fast Exponential Algorithms and Combinatorial Bounds
• On the Number of Complete Subgraphs of a Graph
• Maximal Induced Matchings in Triangle-Free Graphs
• On cliques in graphs
• On cliques in graphs

This page was built for publication: Maximal induced matchings in \(K_4\)-free and \(K_5\)-free graphs