hide
Free keywords:
-
Abstract:
Consider the following generalized notion of graph coloring: a coloring of the
vertices of a graph~$G$ is \emph{valid} \wrt some given graph~$F$ if there is
no copy of $F$ in $G$ whose vertices all receive the same color. We study the
problem of computing valid colorings of the binomial random graph~$\Gnp$ on~$n$
vertices with edge probability~$p=p(n)$ in the following online setting: the
vertices of an initially hidden instance of $\Gnp$ are revealed one by one
(together with all edges leading to previously revealed vertices) and have to
be colored immediately and irrevocably with one of $r$ available colors.
It is known that for any fixed graph $F$ and any fixed integer $r\geq 2$ this
problem has a threshold $p_0(F,r,n)$ in the following sense: For any function
$p(n) = o(p_0)$ there is a strategy that \aas (asymptotically almost surely,
i.e., with probability tending to 1 as $n$ tends to infinity) finds an
$r$-coloring of $\Gnp$ that is valid \wrt $F$ online, and for any
function~$p(n)=\omega(p_0)$ \emph{any} online strategy will \aas fail to do so.
In this work we establish a general correspondence between this probabilistic
problem and a deterministic two-player game in which the random process is
replaced by an adversary that is subject to certain restrictions inherited from
the random setting. This characterization allows us to compute, for any $F$ and
$r$, a value $\gamma=\gamma(F,r)$ such that the threshold of the probabilistic
problem is given by $p_0(F,r,n)=n^{-\gamma}$. Our approach yields
polynomial-time coloring algorithms that \aas find valid colorings of $\Gnp$
online in the entire regime below the respective thresholds, i.e., for any
$p(n) = o(n^{-\gamma})$.
