Asymptotically optimal frugal colouring

ABSTRACT

We prove that every graph with maximum degree Δ can be properly (Δ + 1)-coloured so that no colour appears more than O(log Δ / log log Δ) times in the neighbourhood of any vertex. This is best possible up to the constant factor in the O(−) term. We also provide an efficient algorithm to produce such a colouring.

REFERENCES

• 1: O. Amini, L. Esperet and J. van den Heuvel, Frugal Colouring of Graphs. CDAM Research Report CDAM-LSE-2007-11 (2007).
• 2: J. Beck, An algorithmic approach to the Lovasz Local Lemma. Rand. Str. & Alg. 2, 343--365 (1991).
• 3: H. Chernoff, A measure of asymptotic efficiency for tests of a hypothesis based on the sum of observations. Ann. Math. Statist. 23 493--509 (1952).
• 4: P. Erdős and L. Lovász, Problems and Results on 3-Chromatic Hypergraphs and Some Related Questions. In: "Infinite and Finite Sets" (A. Hajnal et. al. Eds), Colloq. Math. Soc. J. Bolyai 11, North Holland, Amsterdam, 609--627 (1975).
• 5: P. Erdős and J. Selfridge, On a combinatorial game. J. Comb. Th. (A) 14 298--301 (1973).
• 6: Paul Erdős , Joel Spencer, Lopsided Lova´sz Local Lemma and Latin transversals, Discrete Applied Mathematics, v.30 n.2-3, p.151-154, Feb. 28, 1991
• 7: H. Hind, M. Molloy and B. Reed, Colouring a graph frugally. Combinatorica 17 469--482 (1997).
• 8: H. Hind, M. Molloy and B. Reed, Total colouring with Δ+poly(log Δ) colours. SIAM J. Computing 28 816--821 (1998).
• 9: T. Jensen and B. Toft, Graph Colouring Problems. Wiley, New York (1995).
• 10: J. Kahn, Asymptotics of the list chromatic index for hypergraphs. Rand. Struc. & Alg. 17 117--155 (2000).
• 11: Colin McDiarmid, Concentration for Independent Permutations, Combinatorics, Probability and Computing, v.11 n.2, p.163-178, March 2002 [doi>10.1017/S0963548301005089]
• 12: M. Molloy and B. Reed, A bound on the total chromatic number. Combinatorica 18 241--280 (1998).
• 13: Michael Molloy , Bruce Reed, Further algorithmic aspects of the local lemma, Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.524-529, May 24-26, 1998, Dallas, Texas, United States [doi>10.1145/276698.276866]
• 14: Michael Molloy , Bruce Reed, Colouring Graphs whose Chromatic Number Is Almost Their Maximum Degree, Proceedings of the Third Latin American Symposium on Theoretical Informatics, p.216-225, April 20-24, 1998
• 15: M. Molloy and B. Reed, Graph Colouring and the Probabilistic Method. Springer (2001).
• 16: M. Molloy and B. Reed, Colouring graphs when the number of colours is almost the maximum degree. In preparation. Preliminary version in: Proceedings of the 33rd ACM Symposium on Computing (2001).
• 17: S. Pemmaraju and A. Srinivasan, The randomized coloring procedure with symmetry-breaking. To appear in Proceedings of APPROX (2008).
• 18: B. Reed, ω, Δ, and χ, Journal of Graph Theory, v.27 n.4, p.177-212, April 1998 [doi>10.1002/(SICI)1097-0118(199804)27:4<>1.0.CO;2-7]
• 19: Bruce Reed, A strengthening of Brooks' theorem, Journal of Combinatorial Theory Series B, v.76 n.2, p.136-149, July 1999 [doi>10.1006/jctb.1998.1891]
• 20: Aravind Srinivasan, Improved algorithmic versions of the Lovász Local Lemma, Proceedings of the nineteenth annual ACM-SIAM symposium on Discrete algorithms, p.611-620, January 20-22, 2008, San Francisco, California
• 21: M. Talagrand, Concentration of measure and isoperimetric inequalities in product spaces. Instutut Des Hautes Etudes Scientifiques, Publications Mathematiques 81, 73--205 (1995).
• 22: Raphael Yuster, Linear coloring of graphs, Discrete Mathematics, v.185 n.1-3, p.293-297, Apr. 15 1998 [doi>10.1016/S0012-365X(97)00209-4]

INDEX TERMS

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

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

  I. Computing Methodologies
  I.1 SYMBOLIC AND ALGEBRAIC MANIPULATION
      I.1.2 Algorithms
          Subjects: Analysis of algorithms