Bukh, Boris


Coloring random subgraphs ★★

Author(s): Bukh

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$.

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

Keywords: coloring; random graph

Syndicate content