CJO - Abstract - Packing Cliques in Graphs with Independence Number 2

Cambridge Journals Online

Cambridge Journals Online
Skip to content
Combinatorics, Probability and Computing (2007), 16 : 805-817 Cambridge University Press
doi:10.1017/S0963548306008194 (About doi)
Published online by Cambridge University Press 03 Nov 2006
 
Cambridge Journals Online - CUP Full-Text Page
Combinatorics, Probability and Computing (2007), 16:805-817 Cambridge University Press
Copyright © Cambridge University Press 2006
doi:10.1017/S0963548306008194

Paper

Packing Cliques in Graphs with Independence Number 2

RAPHAEL YUSTERa1

a1 Department of Mathematics, University of Haifa, Haifa 31905, Israel (e-mail: raphy@research.haifa.ac.il)
Article author query
yuster r Google Scholar

Abstract

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.

(Received October 11 2005)

(Revised August 01 2006)

back to top
Cambridge University Press