Home » Subject » Graph Theory » Probabilistic G.T.

Coloring random subgraphs

Importance: Medium ✭✭
Author(s): Bukh, Boris
Subject: Graph Theory
» Probabilistic Graph Theory
Keywords: coloring
random graph
Recomm. for undergrads: no
Posted by: mdevos
on: June 18th, 2008

If $ G $ is a graph and $ p \in [0,1] $, we let $ G_p $ denote a subgraph of $ G $ where each edge of $ G $ appears in $ G_p $ with independently with probability $ p $.

Problem   Does there exist a constant $ c $ so that $ {\mathbb E}(\chi(G_{1/2})) > c \frac{\chi(G)}{\log \chi(G)} $?

It is a classical result that the above problem has a positive answer when $ G $ is the complete graph. More generally, the lower bound $ {\mathbb E}(\chi(G_{1/2})) \ge c \frac{\chi(G)}{\log |V(G)|} $ is known.

It is easy to obtain the bound $ {\mathbb E}(\chi(G_{1/2})) \ge (\chi(G))^{1/2} $, since we may imagine forming two random subgraphs $ H,H' $ of $ G $ by putting each edge of $ G $ in either $ H $ or $ H' $ independently with probability $ 1/2 $. Then $ \chi(H) \chi(H') \ge \chi(G) $ and this gives the desired bound. A similar argument with three subgraphs shows that $ {\mathbb E}(\chi(G_{1/3})) \ge (\chi(G))^{1/3} $, however these arguments all seem to require integer multiples, so the best known lower bound on $ {\mathbb E}(\chi(G_{49/100})) $ of this form is $ (\chi(G))^{1/3} $.

Bibliography

*[B] Boris Bukh's problem page.


* indicates original appearance(s) of problem.
add new comment

No?

On June 4th, 2009 chrisrudy502 says:

I haven't worked through the details yet, but what if $ G $ is the union of $ K_n $ and a sufficiently huge bipartite graph $ H $? Then $ \chi(G) = n $, and by taking $ H $ huge enough, you can get $ \mathbb{E}(\chi(G_{1/2})) $ as close to 2 as you like, forcing $ c $ as small as you like.

EDIT: Whoo boy. Nevermind.

reply

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.