1
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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...

$\endgroup$
3
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.