Critical chromatic number and the complexity of perfect packings in graphs

ABSTRACT

Let H be any non-bipartite graph. We determine asymptotically the minimum degree of a graph G which ensures that G has a perfect H-packing. More precisely, we determine the smallest number τ having the following property: For every positive constant γ there exists an integer n0 = n0(γ, H) such that every graph G whose order n ≥n0 is divisible by |H| and whose minimum degree is at least (τ + γ) n contains a perfect H-packing. The value of τ depends on the relative sizes of the colour classes in the optimal colourings of H. The proof is algorithmic, which shows that the problem of finding a maximum H-packing is polynomially solvable for graphs G whose minimum degree is at least (τ + γ)n. On the other hand, given any positive constant γ, we show that for infinitely many (non-bipartite) graphs H the corresponding decision problem becomes NP-complete if one considers input graphs G of minimum degree at least (τ - γ)n.

REFERENCES

• 1: N. Alon , R. A. Duke , H. Lefmann , V. Rödl , R. Yuster, The algorithmic aspects of the regularity lemma, Journal of Algorithms, v.16 n.1, p.80-109, Jan. 1994 [doi>10.1006/jagm.1994.1005]
• 2: N. Alon and J. Spencer, The Probabilistic Method (2nd edition), Wiley-Interscience 2000.
• 3: Noga Alon , Raphael Yuster, H-factors in dense graphs, Journal of Combinatorial Theory Series B, v.66 n.2, p.269-282, March 1996 [doi>10.1006/jctb.1996.0020]
• 4: B. Bollobás, Modern Graph Theory, Graduate Texts in Mathematics 184, Springer-Verlag 1998.
• 5: B.S. Baker, Approximation algorithms for NP-complete problems on planar graphs, Proc. 24th Ann. IEEE Symp. on Foundations of Computer Science (1983), 265--273.
• 6: Fran Berman , David Johnson , Tom Leighton , Peter W. Shor , Larry Snyder, Generalized planar matching, Journal of Algorithms, v.11 n.2, p.153-184, Jun. 1990 [doi>10.1016/0196-6774(90)90001-U]
• 7: R. Diestel, Graph Theory, Graduate Texts in Mathematics 173, Springer-Verlag 1997.
• 8: P. Hell and D. G. Kirkpatrick, Scheduling, matching and colouring, Colloquia Math. Soc. Bolyai25 (1978), 273--279.
• 9: P. Hell and D. G. Kirkpatrick, On the complexity of general graph factor problems, SIAM J. Computing12 (1983), 601--609.
• 10: C. A. J. Hurkens , A. Schrijver, On the size of systems of sets every t of which have an SDR, with an application to the worst-case ratio of heuristics for packing problems, SIAM Journal on Discrete Mathematics, v.2 n.1, p.68-72, February 1989 [doi>10.1137/0402008]
• 11: Viggo Kann, Maximum bounded H-matching is Max SNP-complete, Information Processing Letters, v.49 n.6, p.309-318, March 22, 1994 [doi>10.1016/0020-0190(94)90105-8]
• 12: K. Kawarabayashi, K4--factors in a graph, J. Graph Theory39 (2002), 111--128.
• 13: János Komlós, The Blow-up Lemma, Combinatorics, Probability and Computing, v.8 n.1-2, p.161-176, January 1999
• 14: J. Komlós, Tiling Turán theorems, Combinatorica20 (2000), 203--218.
• 15: J. Komlós, G. N. Sárközy and E. Szemerédi, Blow-up lemma, Combinatorica17 (1997), 109--123.
• 16: János Komlós , Gabor N. Sarkozy , Endre Szemerédi, An algorithmic version of the blow-up lemma, Random Structures & Algorithms, v.12 n.3, p.297-310, May 1998 [doi>10.1002/(SICI)1098-2418(199805)12:3<297::AID-RSA5>3.0.CO;2-Q]
• 17: János Komlós , Gábor N. Sárközy , Endre Szemerédi, Proof of the Alon—Yuster conjecture, Discrete Mathematics, v.235 n.1-3, p.255-269, May 28 2001 [doi>10.1016/S0012-365X(00)00279-X]
• 18: J. Komlós and M. Simonovits, Szemerédi's Regularity Lemma and its applications in graph theory, Bolyai Society Mathematical Studies 2, Combinatorics, Paul Erdős is Eighty (Vol. 2) (D. Miklós, V. T. Sós and T. Szőnyi eds.), Budapest (1996), 295--352.
• 19: D. Kühn and D. Osthus, Perfect Kl-packings in graphs, submitted.
• 20: D. Kühn and D. Osthus, The minimum degree threshold for perfect graph packings, in preparation.
• 21: D. Kühn, D. Osthus and A. Taraz, Large planar subgraphs in dense graphs, J. Combin. Theory B, to appear.
• 22: A. Shokoufandeh and Y. Zhao, Proof of a conjecture of Komlós, Random Struct. Alg.23 (2003) 180--205.

INDEX TERMS

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

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.1 Numerical Algorithms and Problems
          Subjects: Number-theoretic computations (e.g., factoring, primality testing)
      F.2.2 Nonnumerical Algorithms and Problems

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.1 Combinatorics
          Subjects: Counting problems

General Terms:
Algorithms, Theory