Paper Info
Title
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})] geq 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 leq k^{1/3}$ it holds that $Pr[chi(G_{1/2}) leq d] u003c exp left(- Omegaleft(frac{k(k-d^3)}{d^3}right)right)$. In particular, $Pr[G_{1/2} text{ is bipartite}] u003c 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 $Pr[chi(G_{1/2}) leq d] u003c e^{- Omegaleft(tright)}$. We also prove that for any graph $G$ with chromatic number $k = chi(G)$ and independence number $alpha(G) leq O(n/k)$ it holds that $mathbb{E}[chi(G_{1/2})] geq Omega left( k/log(k) right)$. This gives a positive answer to the question of Bukh for a large family of graphs.
Year
Venue
Field
2016
arXiv: Combinatorics
Discrete mathematics,Complete graph,Graph,Combinatorics,Independence number,Vertex (geometry),Bipartite graph,Omega,Mathematics
DocType
Volume
Citations 
Journal
abs/1612.04319
0
PageRank 
References 
Authors
0.34
0
1
Name
Order
Citations
PageRank
Igor Shinkar1248.97