Counterexamples to Gerbner's Conjecture on Stability of Maximal $F$-free Graphs

Abstract

Let $F$ be an $(r+1)$-color critical graph with $r\ge 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\ge 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$.

20pages,1 figures