论文标题
对Gerbner关于最大$ f $ - 免费图的稳定性的猜想的反面样本
Counterexamples to Gerbner's Conjecture on Stability of Maximal $F$-free Graphs
论文作者
论文摘要
令$ f $为$（r+1）$ - 颜色关键图，带有$ r \ geq 2 $，即$χ（f）= r+1 $，并且在$ f $中有一个边缘$ e $ $χ（f-e）= r $。 Gerbner最近指出，每$ n $ vertex Maximal $ f $ -fre-free Graph至少具有$（1- \ frac {1} {1} {r} {r}）\ frac {n^2} {2} {2} {2} {n^{n^{\ frac {\ frac {r+1} {r+1} {r+1} {r+1} $ - 顶点。令$ f_ {s，k} $是通过共享共同边缘从$ c_ {2k+1} $获得的$ s $副本获得的图。在本文中，我们表明，对于所有$ k \ geq 2 $，如果$ g $是$ n $ -vertex maximal $ f_ {s，k} $ - 至少$ n^{2}/4- o（n^{n^{\ frac {\ frac {s+2}} {s+1}} {s+1}} {s+1}} {顶点。我们还表明这是最好的。这反驳了Gerbner的猜想，以$ r = 2 $。
Let $F$ be an $(r+1)$-color critical graph with $r\geq 2$, that is, $χ(F)=r+1$ and there is an edge $e$ in $F$ such that $χ(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$.
