On Coloring Random Subgraphs of a Fixed Graph

Publication date 13 December 2016

Abstract: Given an arbitrary graph

G

we study the chromatic number of a random subgraph

G_{1 / 2}

obtained from

G

by removing each edge independently with probability

1 / 2

. Studying

c h i (G_{1 / 2})

has been suggested by Bukh~cite{Bukh}, who asked whether

m a t h b b E [c h i (G_{1 / 2})] g e q O m e g a (c h i (G) / l o g (c h i (G)))

holds for all graphs

G

. In this paper we show that for any graph

G

with chromatic number

k = c h i (G)

and for all

d l e q k^{1 / 3}

it holds that

P r [c h i (G_{1 / 2}) l e q d] < e x p l e f t (- O m e g a l e f t (f r a c k (k - d^{3}) d^{3} i g h t) i g h t)

. In particular,

P r [G_{1 / 2} e x t i s b i p a r t i t e] < e x p l e f t (- O m e g a l e f t (k^{2} i g h t) i g h t)

. The later bound is tight up to a constant in

O m e g a (c d o t)

, and is attained when

G

is the complete graph on

k

vertices. As a technical lemma, that may be of independent interest, we prove that if in emph{any}

d^{3}

coloring of the vertices of

G

there are at least

t

monochromatic edges, then

P r [c h i (G_{1 / 2}) l e q d] < e^{- O m e g a l e f t (t i g h t)}

. We also prove that for any graph

G

with chromatic number

k = c h i (G)

and independence number

a l p h a (G) l e q O (n / k)

it holds that

m a t h b b E [c h i (G_{1 / 2})] g e q O m e g a l e f t (k / l o g (k) i g h t)

. This gives a positive answer to the question of Bukh for a large family of graphs.

This page was built for publication: On Coloring Random Subgraphs of a Fixed Graph