TY - CHAP
T1 - The Randomized Coloring Procedure with Symmetry-Breaking
T2 - Automata, Languages and ProgrammingAutomata, Languages and Programming
Y1 - 2008
A1 - Pemmaraju,Sriram
A1 - Srinivasan, Aravind
ED - Aceto,Luca
ED - Damgård,Ivan
ED - Goldberg,Leslie
ED - Halldórsson,Magnús
ED - Ingólfsdóttir,Anna
ED - Walukiewicz,Igor
AB - A basic randomized coloring procedure has been used in probabilistic proofs to obtain remarkably strong results on graph coloring. These results include the asymptotic version of the List Coloring Conjecture due to Kahn, the extensions of Brooks’ Theorem to sparse graphs due to Kim and Johansson, and Luby’s fast parallel and distributed algorithms for graph coloring. The most challenging aspect of a typical probabilistic proof is showing adequate concentration bounds for key random variables. In this paper, we present a simple symmetry-breaking augmentation to the randomized coloring procedure that works well in conjunction with Azuma’s Martingale Inequality to easily yield the requisite concentration bounds. We use this approach to obtain a number of results in two areas: frugal coloring and weighted equitable coloring . A β-frugal coloring of a graph G is a proper vertex-coloring of G in which no color appears more than β times in any neighborhood. Let G = ( V , E ) be a vertex-weighted graph with weight function w : V →[0, 1] and let W = ∑ v ∈ V w ( v ). A weighted equitable coloring of G is a proper k -coloring such that the total weight of every color class is “large”, i.e., “not much smaller” than W / k ; this notion is useful in obtaining tail bounds for sums of dependent random variables.
JA - Automata, Languages and ProgrammingAutomata, Languages and Programming
T3 - Lecture Notes in Computer Science
PB - Springer Berlin / Heidelberg
VL - 5125
SN - 978-3-540-70574-1
UR - http://dx.doi.org/10.1007/978-3-540-70575-8_26
ER -