Hostname: page-component-74656f9884-rdgjk Total loading time: 0 Render date: 2026-11-09T14:37:29.851Z Has data issue: false hasContentIssue false
  • English
  • Français

Packing Cliques in Graphs with Independence Number 2

Published online by Cambridge University Press:  01 September 2007

RAPHAEL YUSTER
RAPHAEL YUSTER*
Affiliation:
Department of Mathematics, University of Haifa, Haifa 31905, Israel (e-mail: raphy@research.haifa.ac.il)
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

Let G be a graph with no three independent vertices. How many edges of G can be packed with edge-disjoint copies of Kk? More specifically, let fk(n, m) be the largest integer t such that, for any graph with n vertices, m edges, and independence number 2, at least t edges can be packed with edge-disjoint copies of Kk. Turán's theorem together with Wilson's Theorem assert that $f_k(n,m)=(1-o(1))\frac{n^2}{4}$ if $m \approx \frac{n^2}{4}$. A conjecture of Erdős states that $f_3(n,m) \geq (1-o(1))\frac{n^2}{4}$ for all plausible m. For any ε > 0, this conjecture was open even if $m \leq n^2(\frac{1}{4}+\epsilon)$. Generally, f_k(n,m) may be significantly smaller than $\frac{n^2}{4}$. Indeed, for k=7 it is easy to show that $f_7(n,m) \leq \frac{21}{90}{n^2}$ for m ≈ 0.3n2. Nevertheless, we prove the following result. For every k≥ 3 there exists γ>0 such that if $m \leq n^2(\frac{1}{4}+\gamma)$ then $f_k(n,m) \geq (1-o(1))\frac{n^2}{4}$. In the special case k=3 we obtain the reasonable bound γ ≥ 10−4. In particular, the above conjecture of Erdős holds whenever G has fewer than 0.2501n2 edges.

Information

Type
Paper
Information
Combinatorics, Probability and Computing , Volume 16 , Issue 5 , September 2007 , pp. 805 - 817
Copyright
Copyright © Cambridge University Press 2006

References

[1]Bollobás, B. (1998) Modern Graph Theory, Springer.CrossRefGoogle Scholar
[2]Erdős, P. (1997) Some recent problems and results in graph theory. Discrete Math. 164 81–85.CrossRefGoogle Scholar
[3]Erdős, P., Faudree, R. J., Gould, R. J., Jacobson, M. S. and Lehel, J. (2001) Edge disjoint monochromatic triangles in 2-colored graphs. Discrete Math. 231 135–141.CrossRefGoogle Scholar
[4]Haxell, P. E. and Rödl, V. (2001) Integer and fractional packings in dense graphs. Combinatorica 21 13–38.CrossRefGoogle Scholar
[5]Keevash, P. and Sudakov, B. (2004) Packing triangles in a graph and its complement. J. Graph Theory 47 203–216.CrossRefGoogle Scholar
[6]Simonovits, M. (1968) A method for solving extremal problems in graph theory, stability problems. In Theory of Graphs (Proc. Colloq. Tihany, 1966), Academic Press, New York, and Akad. Kiadó, Budapest, pp. 279–319.Google Scholar
[7]Wilson, R. M. (1975) Decomposition of complete graphs into subgraphs isomorphic to a given graph. Congressus Numerantium XV 647–659.Google Scholar
[8]Yuster, R.(2005) Asymptotically optimal K k-packings of dense graphs via fractional K k-decompositions. J. Combin. Theory Ser. B 95 1–11.CrossRefGoogle Scholar
[9]Yuster, R. (2005) Integer and fractional packing of families of graphs. Random Struct. Alg. 26 110–118.CrossRefGoogle Scholar