Home ยป Coloring random subgraphs

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

Comments are limited to a maximum of 1000 characters.
More information about formatting options