Coloring random graphs online without creating monochromatic subgraphs
METADATA ONLY
Author / Producer
Date
2011
Publication Type
Conference Paper
ETH Bibliography
yes
Citations
Altmetric
METADATA ONLY
Data
Rights / License
Abstract
Consider the following generalized notion of graph coloring: a coloring of the vertices of a graph G is valid w.r.t. 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 Gn,p on n vertices with edge probability p = p(n) in the following online setting: the vertices of an initially hidden instance of Gn,p 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 ≥ 2 this problem has a threshold po (F, r, n) in the following sense: For any function p(n) = o(po) there is a strategy that a.a.s. (asymptotically almost surely, i.e., with probability tending to 1 as n tends to infinity) finds an r-coloring of Gn,p that is valid w.r.t. F online, and for any function p(n) = ω(po) any online strategy will a.a.s. 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 γ = γ(F, r) such that the threshold of the probabilistic problem is given by po(F, r, n) = n−γ. Our approach yields polynomial-time coloring algorithms that a.a.s. find valid colorings of Gn,p online in the entire regime below the respective thresholds, i.e., for any p(n) = o(n-γ).
Permanent link
Publication status
published
Editor
Book title
SODA '11: Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms
Journal / series
Volume
Pages / Article No.
145 - 158
Publisher
SIAM
Event
22nd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2011)
Edition / version
Methods
Software
Geographic location
Date collected
Date created
Subject
Organisational unit
03672 - Steger, Angelika / Steger, Angelika