Almost all graphs with average degree 4 are 3-colorable

ABSTRACT

The technique of using differential equations to approximate the mean path of Markov chains has proved very useful in the average-case analysis of algorithms. Here, we significantly expand the range of this technique, by showing that it can be used to handle algorithms that favor high-degree vertices. In particular, we consider the problem of 3-coloring sparse random graphs and analyze a "smoothed" version of the Brelaz heuristic. This allows us to prove that i) almost all graphs with average degree d, i.e. G(n,p=d/n), are 3-colorable for d&xie; 4.03, and that ii) almost all 4-regular graphs are 3-colorable. This improves over the previous lower bound of 3.847 for the G(n,p) 3-colorability threshold and gives the first non trivial result on the 3-colorability of random regular graphs.

REFERENCES

• 1: Dimitris Achlioptas, Setting 2 variables at a time yields a new lower bound for random 3-SAT (extended abstract), Proceedings of the thirty-second annual ACM symposium on Theory of computing, p.28-37, May 21-23, 2000, Portland, Oregon, United States [doi>10.1145/335305.335309]
• 2: Dimitris Achlioptas , Ehud Friedgut, A sharp threshold for k-colorability, Random Structures & Algorithms, v.14 n.1, p.63-70, Jan. 1999 [doi>10.1002/(SICI)1098-2418(1999010)14:1<63::AID-RSA3>3.0.CO;2-7]
• 3: D. Achlioptas , M. Molloy, The analysis of a list-coloring algorithm on a random graph, Proceedings of the 38th Annual Symposium on Foundations of Computer Science (FOCS '97), p.204, October 19-22, 1997
• 4: N. Alon and J. H. Spencer. The probabilistic method. John Wiley & Sons, Inc., New York, 1992.
• 5: K. Athreya. Personal Communication.
• 6: E. Bender and E. Canfield. The asymptotic number of labelled graphs with given degree sequences. J. Combin. Theory Ser. A, (24):296--307, 1978.
• 7: S. Boettcher and A. Percus. Optimization with extremal dynamics. Phys. Rev. Lett., (86):5211--5214, 2001.
• 8: B. Bollobás. Random graphs. Academic Press, London-New York, 1985.
• 9: Daniel Brélaz, New methods to color the vertices of a graph, Communications of the ACM, v.22 n.4, p.251-256, April 1979 [doi>10.1145/359094.359101]
• 10: P. Erdós and A. Rényi. On the evolution of random graphs. Magyar Tud. Akad. Mat. Kutató Int. Közl., 5:17--61, 1960.
• 11: Alan Frieze , Stephen Suen, Analysis of two simple heuristics on a random instance of k-SAT, Journal of Algorithms, v.20 n.2, p.312-355, March 1996 [doi>10.1006/jagm.1996.0016]
• 12: A. C. Kaporis, L. M. Kirousis, and Y. C. Stamatiou. A note on the non-colorability threshold of a random graph. Electron. J. Combin., 7:R29, 2000.
• 13: R. Karp and M. Sipser. Maximum matchings in sparse random graphs. In 22nd Annual Symposium on Foundations of Computer Science, pages 364--375.
• 14: T. G. Kurtz. Solutions of ordinary differential equations as limits of pure jump Markov processes. J. Appl. Probability, 7:49--58, 1970.
• 15: T. G. Kurtz. Approximation of population processes. Society for Industrial and Applied (MATH)ematics (SIAM), Philadelphia, Pa., 1981.
• 16: Michael Mitzenmacher, Studying Balanced Allocations with Differential Equations, Combinatorics, Probability and Computing, v.8 n.5, p.473-482, September 1999 [doi>10.1017/S0963548399003946]
• 17: M. Mitzenmacher. Analyses of load stealing models based on families of differential equations. Theory Comput. Syst., 34(1):77--98, 2001.
• 18: C. J. Mode. Multitype branching processes. Theory and applications. American Elsevier Publishing Co., Inc., New York, 1971.
• 19: M. Molloy. Random graphs on a fixed degree sequence. Ph.D Thesis, Carnegie Mellon University, 1995.
• 20: Michael Molloy , Bruce Reed, A critical point for random graphs with a given degree sequence, Random Structures & Algorithms, v.6 n.2-3, p.161-179, March-May 1995
• 21: Boris Pittel , Joel Spencer , Nicholas Wormald, Sudden emergence of a giant k-core in a random graph, Journal of Combinatorial Theory Series B, v.67 n.1, p.111-151, May 1996 [doi>10.1006/jctb.1996.0036]
• 22: N. Wormald. Some Problems in the Enumeration of Labelled Graphs. Ph.D. Thesis, Newcastle University, 1978.
• 23: N. C. Wormald. Differential equations for random processes and random graphs. Ann. Appl. Probab., 5(4):1217--1235, 1995.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Graph algorithms

Additional Classification:
  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS
      Subjects: Probabilistic algorithms (including Monte Carlo)

Keywords:
graph coloring, random graphs, threshold phenomena