2016/12/13 by Igor Shinkar, Shinkar, Igor · 1 citation
Mathematics · Computer Science · #Limits and Structures in Graph Theory #Advanced Graph Theory Research #Graph Labeling and Dimension Problems
paper · pdf · doi:10.48550/arxiv.1612.04319
Given an arbitrary graph G we study the chromatic number of a random subgraph G1/2 obtained from G by removing each edge independently with probability 1/2. Studying χ(G1/2) has been suggested by Bukh~\citeBukh, who asked whether 𝔼[χ(G1/2)] ≥ Ω( χ(G)/log(χ(G))) holds for all graphs G. In this paper we show that for any graph G with chromatic number k = χ(G) and for all d ≤ k1/3 it holds that Pr[χ(G1/2) ≤ d] < exp (- Ω((k(k-d3))/(d3))). In particular, Pr[G1/2 is bipartite] < exp (- Ω(k2 )). The later bound is tight up to a constant in Ω(⋅), 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 any d3 coloring of the vertices of G there are at least t monochromatic edges, then Pr[χ(G1/2) ≤ d] < e- Ω(t). We also prove that for any graph G with chromatic number k = χ(G) and independence number α(G) ≤ O(n/k) it holds that 𝔼[χ(G1/2)] ≥ Ω( k/log(k) ). This gives a positive answer to the question of Bukh for a large family of graphs.