Maximal independent sets in clique-free graphs

DOI10.1016/j.ejc.2022.103575zbMath1504.05140arXiv2108.06359OpenAlexW3195989086MaRDI QIDQ2674559

Sam Spiro, Xiaoyu He, Jiaxi Nie

Publication date: 14 September 2022

Published in: European Journal of Combinatorics (Search for Journal in Brave)

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

zbMATH Keywords

rainbow Turán problems for cliquesRuzsa-Szemerédi problem

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Graph theory (including graph drawing) in computer science (68R10) Enumeration in graph theory (05C30) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Cites Work

• Unnamed Item
• The number of maximal independent sets in a connected graph
• On generating all maximal independent sets
• Enumerating all connected maximal common subgraphs in two graphs
• Sharp bound on the number of maximal sum-free subsets of integers
• The number of the maximal triangle-free graphs
• Listing All Maximal Cliques in Sparse Graphs in Near-Optimal Time
• INTERSECTION THEOREMS FOR SYSTEMS OF FINITE SETS
• The Number of Maximal Independent Sets in a Tree
• The number of maximal independent sets in connected graphs
• Generating All Maximal Independent Sets: NP-Hardness and Polynomial-Time Algorithms
• A New Algorithm for Generating All the Maximal Independent Sets
• The Number of Maximal Independent Sets in Triangle-Free Graphs
• An upper bound on the number of cliques in a graph
• Algorithm Theory - SWAT 2004
• An Analysis of Some Graph Theoretical Cluster Techniques
• On cliques in graphs

This page was built for publication: Maximal independent sets in clique-free graphs