Let $G$ be a regular graph having spanning regular subgraphs $G_1,\dots, G_k$ whose edge sets are disjoint and their union is the whole edge set of $G$. Is it true that the clique number of $G$ is bounded above by the sum of clique numbers of $G_i$s? If not, under what conditions the answer is positive.
2 Answers
The edges of $K_{2n+1}$ can be split into $n$ Hamiltonian cycles, whose clique numbers are 2, which gives a counterexample to the initial conjecture. Moreover, these cycles can be merged into larger regular graphs without increasing of the clique number (check, e.g., the case when $2n+1$ is prime!), which provides much larger gap...
Ilya already gave a counterexample. Here is a simple counterexample with a very large gap. The complete graph $K_{2n}$ (clique number $2n$) can be split into two regular graphs. One is two disjoint copies of $K_n$ (clique number $n$) and the other is the complete bipartite graph $K_{n,n}$ (clique number 2).
If $n$ is even, we can continue dividing the complete graphs into two halves. Consider the case of $K_n$ where $n=2^i$. If I calculated correctly, we can keep dividing until we have $i$ subgraphs which are unions of complete bipartite graphs, the sparsest being a matching. The sum of the clique numbers of the subgraphs is only $2i$, compared to $2^i$ for the original complete graph.