On Coloring Random Subgraphs of a Fixed Graph

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 $\chi (G_{1/2})$ has been suggested by Bukh~\cite{Bukh}, who asked whether $\mathbb{E}[\chi (G_{1/2})]\ge \Omega (\chi (G)/\log (\chi (G)))$ holds for all graphs $G$. In this paper we show that for any graph $G$ with chromatic number $k=\chi (G)$ and for all $d\le k^{1/3}$ it holds that $\mathrm{Pr}[\chi (G_{1/2})\le d]<\exp \left(-\Omega \left(\frac{k(k-d^3)}{d^3}\right)\right)$. In particular, $\mathrm{Pr}[G_{1/2}\text{ is bipartite}]<\exp \left(-\Omega \left(k^2\right)\right)$. The later bound is tight up to a constant in $\Omega (\cdot )$, 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 $\mathrm{Pr}[\chi (G_{1/2})\le d]<e^{-\Omega \left(t\right)}$. We also prove that for any graph $G$ with chromatic number $k=\chi (G)$ and independence number $\alpha (G)\le O(n/k)$ it holds that $\mathbb{E}[\chi (G_{1/2})]\ge \Omega \left(k/\log (k)\right)$. This gives a positive answer to the question of Bukh for a large family of graphs.

References in corpus (1)

• Random subgraphs of finite graphs: I. The scaling window under the triangle condition

Cited by in corpus (1)

• On the chromatic number in the stochastic block model