The Randomized Coloring Procedure with Symmetry-Breaking.

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 \textit{Azuma's Martingale Inequality} to easily yield the requisite
concentration bounds. We use this approach to obtain a number of results in
two areas: \textit{frugal coloring} and \textit{weighted equitable
coloring}.