Randomly coloring planar graphs with fewer colors than the maximum degree

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Randomly coloring planar graphs with fewer colors than the maximum degree

Full text

Pdf (201 KB)

Source

Annual ACM Symposium on Theory of Computing archive
Proceedings of the thirty-ninth annual ACM symposium on Theory of computing table of contents

San Diego, California, USA

SESSION: Session 9B table of contents

Pages: 450 - 458

Year of Publication: 2007

ISBN:978-1-59593-631-8

Authors

Thomas P. Hayes	Toyota Technological Institute at Chicago, Chicago, IL
Juan C. Vera	Georgia Institue of Technology: College of Computing, Atlanta, GA
Eric Vigoda	Georgia Institue of Technology: College of Computing, Atlanta, GA

Sponsors

ACM: Association for Computing Machinery
SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 7, Downloads (12 Months): 50, Citation Count: 0

Additional Information:

abstract references index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/1250790.1250857 What is a DOI?

ABSTRACT

We study Markov chains for randomly sampling k-colorings of a graph with maximum degree δ. Our main result is a polynomial upper bound on the mixing time of the single-site update chain knownas the Glauber dynamics for planar graphs when k=Ω(δ/logδ). Our results can be partially extended to the more general case where the maximum eigenvalue of the adjacency matrix of the graphis at most δ^1-ε, for fixed ε > 0.

The main challenge when k ≤ δ + 1 is the possibility of "frozen" vertices, that is, vertices for which only one coloris possible, conditioned on the colors of its neighbors. Indeed, when δ = O(1), even a typical coloring canhave a constant fraction of the vertices frozen.Our proofs rely on recent advances in techniquesfor bounding mixing time using "local uniformity" properties.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	N. Biggs. Algebraic Graph Theory. 2nd Ed., Cambridge Mathematical Library, Cambridge University Press, 1993.
	2	G. Brightwell and P. Winkler. Random Colorings of a Cayley Tree. In Contemporary Combinatorics. Bolyai Society Mathematical Studies, vol. 10. Bollobás, B. (Ed.), 247--276, 2002.
	3	M. Dyer, L. A. Goldberg and M. Jerrum. Systematic Scan for Sampling Colorings. Ann. Applied Prob., 18(1):185--230, 2006.
	4	M. Dyer and A. Frieze. Randomly colouring graphs with lower bounds on girth and maximum degree. Random Struct. Algorithms, 23(2):167--179, 2003.
	5	Martin Dyer , Abraham D. Flaxman , Alan M. Frieze , Eric Vigoda, Randomly coloring sparse random graphs with fewer colors than the maximum degree, Random Structures & Algorithms, v.29 n.4, p.450-465, December 2006 [doi>10.1002/rsa.v29:4]
	6	Martin Dyer , Alan Frieze , Thomas P. Hayes , Eric Vigoda, Randomly Coloring Constant Degree Graphs, Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science (FOCS'04), p.582-589, October 17-19, 2004 [doi>10.1109/FOCS.2004.57]
	7	Martin Dyer , Alistair Sinclair , Eric Vigoda , Dror Weitz, Mixing in time and space for lattice spin systems: A combinatorial view, Random Structures & Algorithms, v.24 n.4, p.461-479, July 2004 [doi>10.1002/rsa.v24:4]
	8	A. Frieze and J. Vera. On randomly colouring locally sparse graphs. Discrete Mathematics and Theoretical Computer Science, 8(1):121--128, 2006.
	9	A. Frieze and E. Vigoda. Survey of Markov Chains for Randomly Sampling Colorings. Combinatorics, Complexity and Chance, Oxford University Press, 2007.
	10	Leslie Ann Goldberg , Russell Martin , Mike Paterson, Random sampling of 3-colorings in ℤ², Random Structures & Algorithms, v.24 n.3, p.279-302, May 2004 [doi>10.1002/rsa.v24:3]
	11	Michael Luby , Dana Randall , Alistair Sinclair, Markov Chain Algorithms for Planar Lattice Structures, SIAM Journal on Computing, v.31 n.1, p.167-192, 2001 [doi>10.1137/S0097539799360355]
	12	Thomas P. Hayes, A simple condition implying rapid mixing of single-site dynamics on spin systems, Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS'06), p.39-46, October 21-24, 2006 [doi>10.1109/FOCS.2006.6]
	13	Thomas P. Hayes , Alistair Sinclair, A general lower bound for mixing of single-site dynamics on graphs, Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science, p.511-520, October 23-25, 2005 [doi>10.1109/SFCS.2005.6]
	14	Tom Hayes , Eric Vigoda, Coupling with the stationary distribution and improved sampling for colorings and independent sets, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, January 23-25, 2005, Vancouver, British Columbia
	15	Mark Jerrum, A very simple algorithm for estimating the number of k-colorings of a low-degree graph, Random Structures & Algorithms, v.7 n.2, p.157-165, September 1995 [doi>10.1002/rsa.3240070205]
	16	A. Johansson, Asymptotic choice number for triangle free graphs, DIMACS Technical Report, 91--95, 1996.
	17	J. Jonasson. Uniqueness of uniform random colorings of regular trees. Statistics & Probability Letters, 57:243--248, 2002.
	18	F. Martinelli. Lectures on Glauber dynamics for Discrete Spin Models. Lecture Notes in Mathematics, vol. 1717, 2000.
	19	F. Martinelli, A. Sinclair and D. Weitz. Fast mixing for independent sets, colorings, and other models on trees. To appear in Random Struct. Algorithms.
	20	Dror Weitz , Alistair Sinclair, Mixing in time and space for discrete spin systems, University of California, Berkeley, 2004