On the size of (K_t, K₁, k)-co-critical graphs

Abstract: Given graphs

G, H_{1}, H_{2}

, we write

G i g h t a r r o w (H_{1}, H_{2})

if every

red, blue

-coloring of the edges of

G

contains a red copy of

H_{1}

or a blue copy of

H_{2}

. A non-complete graph

G

is

(H_{1}, H_{2})

-co-critical if

G r i g h t a r r o w (H_{1}, H_{2})

, but

G + e i g h t a r r o w (H_{1}, H_{2})

for every edge

e

in

o v e r l i n e G

. Motivated by a conjecture of Hanson and Toft from 1987, we study the minimum number of edges over all

(K_{t}, K_{1, k})

-co-critical graphs on

n

vertices. We prove that for all

t g e 3

and

k g e 3

, there exists a constant

e l l (t, k)

such that, for all

n g e (t - 1) k + 1

, if

G

is a

(K_{t}, K_{1, k})

-co-critical graph on

n

vertices, then

e(G)ge left(2t-4+frac{k-1}{2} ight)n-ell(t, k).

Furthermore, this linear bound is asymptotically best possible when

t i n 3, 4, 5

and all

k g e 3

and

n g e (2 t - 2) k + 1

. It seems non-trivial to construct extremal

(K_{t}, K_{1, k})

-co-critical graphs for

t g e 6

. We also obtain the sharp bound for the size of

(K_{3}, K_{1, 3})

-co-critical graphs on

n g e 13

vertices by showing that all such graphs have at least

3 n - 4

edges.

Recommendations

Cites work

Cited in

(7)

This page was built for publication: On the size of \((K_t, K_{1, k})\)-co-critical graphs