# Decomposing complete graphs into clique-free graphs of certain size

Modified in accordance with Tsuyoshi's comment which seems to generalize.

Let $K_{m}$ be a complete graph on $m$ vertices. Is there a way to partition the graphs in to sets of graphs that have no cliques of size $k$ for some $k \in \mathbb{Z}_{+}$? What is the minimum number of partitions would I need to make?

How about the case when $K_{n}$ is replaced by a bipartite $K_{m,n}$ where one seeks a partition such that there is no $K_{k,l}$ for some $k,l \in \mathbb{Z}_{+}$? What is the minimum number of partitions would I need to make?

• !Tsuyoshi Thank you. I think the number $2$ is right in my case. I checked my problem. For me, $m = O(c\log{n})$ where $c \le 3$ and $k = O(\log{n})$. Any decent algorithm should be good for benchmarking! – v s Jul 19 '11 at 15:57