Counterexamples to Gerbner's conjecture on stability of maximal F‐free graphs

Abstract: Let

F

be an

(r + 1)

-color critical graph with

r g e q 2

, that is,

c h i (F) = r + 1

and there is an edge

e

in

F

such that

c h i (F - e) = r

. Gerbner recently conjectured that every

n

-vertex maximal

F

-free graph with at least

(1 - f r a c 1 r) f r a c n^{2} 2 - o (n^{f r a c 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_{2 k + 1}

by sharing a common edge. In this paper, we show that for all

k g e q 2

if

G

is an

n

-vertex maximal

F_{s, k}

-free graph with at least

n^{2} / 4 - o (n^{f r a c 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

.

Recommendations

Cites work

Cited in

(1)

This page was built for publication: Counterexamples to Gerbner's conjecture on stability of maximal F‐free graphs