On the number of maximal independent sets and maximal induced bipartite subgraphs in $K_4$-free graphs

Abstract

Let $G$ be a $K_4$-free graph of order $n$ and let $k$ be an integer with $0\le k\le n$. We show the existence of positive constants $\eta$ and $\nu$ such that $G$ has at most $(4-\eta {)}^{(5-\eta )k-n}(5-\eta {)}^{n-(4-\eta )k}$ maximal independent sets of order $k$ and at most $O\left((12-\nu {)}^{\frac{n}{4}}\right)$ maximal induced bipartite subgraphs.