Randomly coloring planar graphs with fewer colors than the maximum degree

Details Randomly coloring planar graphs with fewer colors than the maximum degree Randomly coloring planar graphs with fewer colors than the maximum degree

2007-06-11

arxiv.org/abs/0706.1530v2

Mathematics

Probability

Preliminary version appeared in STOC 2007. This version contains revised proofs

Scientific paper

We study Markov chains for randomly sampling $k$-colorings of a graph with maximum degree $\Delta$. Our main result is a polynomial upper bound on the mixing time of the single-site update chain known as the Glauber dynamics for planar graphs when $k=\Omega(\Delta/\log{\Delta})$. Our results can be partially extended to the more general case where the maximum eigenvalue of the adjacency matrix of the graph is at most $\Delta^{1-\eps}$, for fixed $\eps > 0$. The main challenge when $k \le \Delta + 1$ is the possibility of "frozen" vertices, that is, vertices for which only one color is possible, conditioned on the colors of its neighbors. Indeed, when $\Delta = O(1)$, even a typical coloring can have a constant fraction of the vertices frozen. Our proofs rely on recent advances in techniques for bounding mixing time using "local uniformity" properties.

Affiliated with

Also associated with

No associations

Rating

Randomly coloring planar graphs with fewer colors than the maximum degree does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Randomly coloring planar graphs with fewer colors than the maximum degree, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Randomly coloring planar graphs with fewer colors than the maximum degree will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-179843