Coloring k-colorable graphs using smaller palettes

ABSTRACT

We obtain the following new coloring results:

• A 3-colorable graph on n vertices with maximum degree &Dgr; can be colored, in polynomial time, using &Ogr;((&Dgr; log &Dgr;)^1/3 ·log n) colors. This slightly improves an &Ogr;((&Dgr;^1/3 log^½ &Dgr;) · log n) bound given by Karger, Motwani and Sudan. More generally, k-colorable graphs with maximum degree &Dgr; can be colored, in polynomial time, using &Ogr;((&Dgr;^1-2/k log^1/k &Dgr;) · log n) colors.

• A 4-colorable graph on n vertices can be colored, in polynomial time, using &Ogr;(n^7/19) colors. This improves an &Ogr;(n^2/5) bound given again by Karger, Motwani and Sudan. More generally, k-colorable graphs on n-vertices can be colored, in polynomial time, using &Ogr;(n^&agr;k) colors, where &agr;5 = 97/207, &agr;6 = 43/79, &agr;7 = 1391/2315, &agr;8 = 175/271, …

The first result is obtained by a slightly more refined probabilistic analysis of the semidefinite programming based coloring algorithm of Karger, Motwani and Sudan. The second result is obtained by combining the coloring algorithm of Karger, Motwani and Sudan, the combinatorial coloring algorithms of Blum and an extension of a technique of Alon and Kahale (which is based on the Karger, Motwani and Sudan algorithm) for finding relatively large independent sets in graphs that are guaranteed to have very large independent sets. The extension of the Alon and Kahale result may be of independent interest.

REFERENCES

• AK98: Noga Alon , Nabil Kahale, Approximating the independence number via the j -function, Mathematical Programming: Series A and B, v.80 n.3, p.253-264, Feb. 1, 1998 [doi>10.1007/BF01581168]
• BK97: Avrim Blum , David Karger, An Õ(n3/14)-coloring algorithm for 3-colorable graphs, Information Processing Letters, v.61 n.1, p.49-53, Jan. 14, 1997 [doi>10.1016/S0020-0190(96)00190-1]
• Blu94: Avrim Blum, New approximation algorithms for graph coloring, Journal of the ACM (JACM), v.41 n.3, p.470-516, May 1994 [doi>10.1145/176584.176586]
• FK96: Uriel Feige , Joe Kilian, Zero Knowledge and the Chromatic Number, Proceedings of the 11th Annual IEEE Conference on Computational Complexity, p.278, May 24-27, 1996
• GK00: Venkatesan Guruswami , Sanjeev Khanna, On the Hardness of 4-Coloring a 3-Colorable Graph, Proceedings of the 15th Annual IEEE Conference on Computational Complexity, p.188, July 04-07, 2000
• GLS93: M. Grotschel, L. Lovasz, and A. Schrijver. Geometric Algorithms and Combinatorial Optimization. Springer Verlag, 1993. Second corrected edition.
• Hal93: Magnús M. Hallórsson, A still better performance guarantee for approximate graph coloring, Information Processing Letters, v.45 n.1, p.19-23, Jan. 25, 1993 [doi>10.1016/0020-0190(93)90246-6]
• KLS00: S. Khanna, N. Linial, and S. Safra. On the hardness of approximating the chromatic number. Combinatorica, 20:393-415, 2000.
• KMS98: 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 [doi>10.1145/274787.274791]
• KNS01: Michael Krivelevich , Ram Nathaniel , Benny Sudakov, Approximating coloring and maximum independent sets in 3-uniform hypergraphs, Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, p.327-328, January 07-09, 2001, Washington, D.C., United States
• KS98: Michael Krivelevich , Benny Sudakov, Approximate Coloring of Uniform Hypergraphs, Certer for Discrete Mathematics & Theoretical Computer Science, 1998
• Lov79: L. Lovasz On the shannon capacity of a graph. IEEE Transactions on Information Theory, IT-25:1- 7, 1979.
• MR99: Sanjeev Mahajan , H. Ramesh, Derandomizing Approximation Algorithms Based on Semidefinite Programming, SIAM Journal on Computing, v.28 n.5, p.1641-1663, April/May 1999 [doi>10.1137/S0097539796309326]
• Wig83: Avi Wigderson, Improving the performance guarantee for approximate graph coloring, Journal of the ACM (JACM), v.30 n.4, p.729-735, Oct. 1983 [doi>10.1145/2157.2158]

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Computations on discrete structures

General Terms:
Algorithms, Theory, Verification