A spectral technique for coloring random 3-colorable graphs (preliminary version)

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

A spectral technique for coloring random 3-colorable graphs (preliminary version)

Full text

Pdf (854 KB)

Source

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

Montreal, Quebec, Canada

Pages: 346 - 355

Year of Publication: 1994

ISBN:0-89791-663-8

Authors

Noga Alon	Institute for Advanced Study, Princeton, NJ and Department of Mathematics, Tel Aviv University, Tel Aviv, Israel
Nabil Kahale	DIMACS, Rutgers University, Piscataway, NJ

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 2, Downloads (12 Months): 22, Citation Count: 4

Additional Information:

references cited by 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/195058.195187 What is a DOI?

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. Alon and J. H. Spencer, The Probabillstic Method, Wiley, 1991.
	2	Avrim Blum, Some tools for approximate 3- coloring, Proc. 31st IEEE FOCS, IEEE (1990), 554-562.
	3	B. Bollob~s, Random Graphs, Academic Press, 1985.
	4	A. Blum and J. H. Spencer, Coloring random and semi-random k-colorable graphs, to appear.
	5	R. Boppana, Ezgenvalues and graph bisection: An average case analysis, Proc. 28th IEEE FOCS, IEEE (1987), 280-285.
	6	Fan R. K. Chung , S.-T. Yau, A near optimal algorithm for edge separators (preliminary version), Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.1-8, May 23-25, 1994, Montreal, Quebec, Canada [doi>10.1145/195058.195077]
	7	M. E. Dyer , A. M. Frieze, The solution of some random NP-hard problems in polynomial expected time, Journal of Algorithms, v.10 n.4, p.451-489, Dec. 1989 [doi>10.1016/0196-6774(89)90001-1]
	8	J. Friedman, On the second eigenvalue and random walks zn random d-regular graphs, Combinatorica 11 (1991), 331-362.
	9	Z. Fiiredi and J. KomlSs, The eigenvalues of random symmetric matrices, Combinatorica 1(1981), 233-241.
	10	J. Friedman , J. Kahn , E. Szemerédi, On the second eigenvalue of random regular graphs, Proceedings of the twenty-first annual ACM symposium on Theory of computing, p.587-598, May 14-17, 1989, Seattle, Washington, United States [doi>10.1145/73007.73063]
	11	D. Karger, R. Motwani and M. Sudan, Improved graph colomng via semzdefinite programming, in preparation.
	12	L. Kucera, Expected behavior of graph colonrzng algorithms, In Lecture Notes in Computer Science No. 55, Springer-Verlag, 1977, pp. 447-451.
	13	A. D. Petford , D. J. Welsh, A randomised 3-colouring algorithm, Discrete Mathematics, v.74 n.1-2, p.253-261, 1989 [doi>10.1016/0012-365X(89)90214-8]
	14	A. Ralston, A First Course in Numerical Analysis, McGraw-Hill, 1985, Section 10.4.
	15	Jonathan S. Turner, Almost all k-colorable graphs are easy to color, Journal of Algorithms, v.9 n.1, p.63-82, March 1988 [doi>10.1016/0196-6774(88)90005-3]

CITED BY 4

	David Karger , Rajeev Motwani , Madhu Sudan, Approximate graph coloring by semidefinite programming, Journal of the ACM (JACM), v.45 n.2, p.246-265, March 1998
	Noga Alon , Michael Krivelevich , Benny Sudakov, Finding a large hidden clique in a random graph, Proceedings of the ninth annual ACM-SIAM symposium on Discrete algorithms, p.594-598, January 25-27, 1998, San Francisco, California, United States
	C. R. Subramanian, List Set Colouring: Bounds and Algorithms, Combinatorics, Probability and Computing, v.16 n.1, p.145-158, January 2007
	C. R. Subramanian, Algorithms for Colouring Random k-colourable Graphs, Combinatorics, Probability and Computing, v.9 n.1, p.45-77, January 2000