Book chapter
The Randomized Coloring Procedure with Symmetry-Breaking
Automata, Languages and Programming, pp.306-319
Lecture Notes in Computer Science, Springer Berlin Heidelberg
2008
DOI: 10.1007/978-3-540-70575-8_26
Abstract
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 ∈ Vw(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.
Details
- Title: Subtitle
- The Randomized Coloring Procedure with Symmetry-Breaking
- Creators
- Sriram Pemmaraju - University of IowaAravind Srinivasan - University of Maryland, College Park
- Resource Type
- Book chapter
- Publication Details
- Automata, Languages and Programming, pp.306-319
- Publisher
- Springer Berlin Heidelberg; Berlin, Heidelberg
- Series
- Lecture Notes in Computer Science
- DOI
- 10.1007/978-3-540-70575-8_26
- eISSN
- 1611-3349
- ISSN
- 0302-9743
- Language
- English
- Date published
- 2008
- Academic Unit
- Computer Science
- Record Identifier
- 9984259492202771
Metrics
8 Record Views