Colouring graphs when the number of colours is nearly the maximum degree

ABSTRACT

We consider for graphs of maximum degree &Dgr;, the problem of determining whether &khgr;G) > &Dgr;-k for various values of k. We obtain sharp theorems characterizing when the barrier to &Dgr;-k colourability must be a local condition, i.e. a small subgraph, and when it can be global. We also show that for large fixed &Dgr;, this problem is either NP-complete or can be solved in linear time, and we determine precisely which values of k correspond to each case prove that Hitting Set with sets of size B is hard to approximate to within a factor $B^{1/19}$. The problem can be approximated to within a factor B [19], and it is the Vertex Cover problem for B=2. The relationship between hardness of approximation and set size seems to have not been explored before.

REFERENCES

• 1: J. Beck, An algorithmic approach to the Lovasz Local Lemma. Rand. Str. and Alg. 2 (1991), 343 - 365.
• 2: A.Beutelspacher and P.R.Hering, Minimal graphs for which the chromatic number equals the maximum degree. Ars. Comb. 18 (1984), 201 - 216.
• 3: O. Borodin and A. Kostochka, On an upper bound on a graph's chromatic number, depending on the graphs's degree and density J.Comb.Th.(B) 23 (1977), 247 - 250.
• 4: R.L. Brooks, On colouring the nodes of a network, Proc. Cambridge Phil. Soc. 37 (1941), 194 - 197.
• 5: Thomas Emden-Weinert , Stefan Hougardy , Bernd Kreuter, Uniquely Colourable Graphs and the Hardness of Colouring Graphs of Large Girth, Combinatorics, Probability and Computing, v.7 n.4, p.375-386, December 1998 [doi>10.1017/S0963548398003678]
• 6: P. Erd} os and L. Lovasz, 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, 1975, 609-627.
• 7: B. Farzad, M. Molloy and B. Reed, in preparation.
• 8: T. Jensen and B. Toft, Graph Coloring Problems, Wiley, 1995.
• 9: Jeff Kahn, Asymptotically good list-colorings, Journal of Combinatorial Theory Series A, v.73 n.1, p.1-59, Jan. 1996 [doi>10.1006/jcta.1996.0001]
• 10: R. Karp, Reducibility among combinatorial problems, In Complexity of Computer Computations, Plenum Press (1972), 85 - 103.
• 11: C. McDiarmid, manuscript.
• 12: Michael Molloy , Bruce Reed, A bound on the strong chromatic index of a graph, Journal of Combinatorial Theory Series B, v.69 n.2, p.103-109, March 1997 [doi>10.1006/jctb.1997.1724]
• 13: M. Molloy and B. Reed, A bound on the total chromatic number, Combinatorica 18 (1998), 241 - 280.
• 14: 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]
• 15: 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
• 16: M. Molloy and B. Reed, Graph Colouring and the Probabilistic Method. Springer (2001).
• 17: B. Reed, x d w and , J.Graph Th., 27 (1998), 177 - 212.
• 18: 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]
• 19: M. Talagrand, Concentration of measure and isoperimetric inequalities in product spaces. Institut Des Hautes Etudes Scientifiques, Publications Mathematiques 81 (1995), 73 - 205.

INDEX TERMS

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

Additional Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.2 Modes of Computation
          Subjects: Probabilistic computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Computations on discrete structures

General Terms:
Algorithms, Performance, Theory, Verification

Keywords:
graph colouring, probabilistic methods