A new approximate graph coloring algorithm

ABSTRACT

Let A be a graph coloring algorithm. Denote by -&-Agrave; (G) the ratio between the maximum number of colors A will use to color the graph G, and the chromatic number of G,x(G). For most existing polynomial coloring algorithms, -&-Agrave;(G) can be as bad as O(n), where n is the number of vertices in G. The best currently known algorithm guarantees -&-Agrave; (G)-&-equil;O(n/logn). In this paper we present a simple and efficient coloring algorithm which guarantees -&-Agrave;(G)-&-le;x(G)n (equation), a considerable improvem-&-edot;nt over the current bounds.

REFERENCES

• 1: Alfred V. Aho , John E. Hopcroft, The Design and Analysis of Computer Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1974
• 2: M. R. Garey , D. S. Johnson, The Complexity of Near-Optimal Graph Coloring, Journal of the ACM (JACM), v.23 n.1, p.43-49, Jan. 1976 [doi>10.1145/321921.321926]
• 3: Harary, F. Graph Theory. Reading, Mass., 1971.
• 4: Johnson, D.S. "Worst case behaviour or graph coloring algorithms", Proc. of the fifth South-Eastern Conference on Combinatorics, Graph Theory and Computing, Utilitas Mathematica Publishing, Winnipeg, Canada, 1974 pp.513-528.
• 5: Karp, R.M. "Reducability among combinatorial problems" in Complexity of Computer Computations, R.E. Miller and J.W. Thatcher, Eds. Plenum Press, New York, 1972 pp. 85-104.
• 6: Matula, D.W., Marble, G. and Issacson, J.D. "Graph coloring algorithms" in R.C. Read (ed.) Graph Theory and Computing, Academic Press, New York, 1972.
• 7: Matula, D.W. "Bounded color functions on graphs" Networks 2 (1972) pp. 29-44.
• 8: Roberts, A.W. and Varberg, D.E. Convex Analysys, Academic press, New York and London, 1973. pp 211-216.
• 9: Larry Stockmeyer, Planar 3-colorability is polynomial complete, ACM SIGACT News, v.5 n.3, p.19-25, July 1973 [doi>10.1145/1008293.1008294]
• 10: Welsh, D.J.A. and Powel, M.B. "An upper bound to the chromatic number of a graph and its application to time tabling problems", The Computer Journal, 10 (1967) pp. 85-86.
• 11: Williams, M.R. "The coloring of very large graphs" in Combinatorial Structures and their Applications, Gordon and Breach, New York (1970).