Let $F$ be an $(r+1)$-color critical graph with $r\geq 2$, that is, $\chi(F)=r+1$ and there is an edge $e$ in $F$ such that $\chi(F-e)=r$. Gerbner recently conjectured that every $n$-vertex maximal $F$-free graph with at least $(1-\frac{ 1}{ r})\frac{ n^2}{ 2}- o(n^{ \frac{ r+1}{ r}})$ edges contains an induced complete $r$-partite graph on $n-o(n)$ vertices. Let $F_{ s,k}$ be a graph obtained from $s$ copies of $C_{ 2k+1}$ by sharing a common edge. In this paper, we show that for all $k\geq 2$ if $G$ is an $n$-vertex maximal $F_{ s,k}$-free graph with at least $n^{ 2}/4 - o(n^{ \frac{ s+2}{ s+1}})$ edges, then $G$ contains an induced complete bipartite graph on $n-o(n)$ vertices. We also show that it is best possible. This disproves Gerbner's conjecture for $r=2$.
Categories: math.CO