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?
Decomposing complete graphs into clique-free graphs of certain size
graph theory;co.combinatorics;graph algorithms;clique;ramsey theory
This question is about Ramsey theory.  In the case of the complete graphs, you can take a=1 by considering partitioning into only two sets.The Ramsey number R(k,k) is the minimum integer m such that however you partition the edges of the complete graph Km into two sets, at least one of the sets contains Kk as a subgraph.  This immediately implies that if m < R(k,k), then the edges of the complete graph Km can be partitioned into two sets so that neither set contains Kk as a subgraph.Erds proved that R(k,k) grows exponentially: R(k,k) > k2k/2/(e2).  This means that if m is sufficiently large, then m < R(k,k) for k = 2 log2m = O(log m).  In other words, you can take a=1 with two sets.