On the number of maximal independent sets and maximal induced bipartite subgraphs in $K_4$-free graphs
Preprint
Abstract
Let $G$ be a $K_4$-free graph of order $n$ and let $k$ be an integer with $0\leq k\leq n$. We show the existence of positive constants $η$ and $ν$ such that $G$ has at most $(4-η)^{(5-η)k-n}(5-η)^{n-(4-η)k}$ maximal independent sets of order $k$ and at most $O\left((12-ν)^{\frac{n}{4}}\right)$ maximal induced bipartite subgraphs.
Keywords
All Related Versions
This publication has 6 references indexed in Scilit:
- On the number of maximal independent sets: From Moon–Moser to Hujter–TuzaJournal of Graph Theory, 2023
- Maximal independent sets in clique-free graphsEuropean Journal of Combinatorics, 2022
- On the number of maximal independent sets in a graphDiscrete Mathematics & Theoretical Computer Science, 2011
- On the number of maximal bipartite subgraphs of a graphJournal of Graph Theory, 2004
- Small Maximal Independent Sets and Faster Exact Graph ColoringJournal of Graph Algorithms and Applications, 2003
- On the Number of Maximal Independent Sets in a GraphBRICS Report Series, 2002