# Maximum clique size of an edge disjoint union

Suppose $$G=(V,E)$$ is a simple but not necessarily finite graph, and let $$E',E''$$ be a disjoint partitioning of $$E$$ into two (not necessarily finite) subsets, so that $$G$$ is the edge disjoint union of the graphs $$G'=(V,E')$$ and $$G''=(V,E'')$$.

My (admittedly vague) question is: when can the maximum clique size of $$G$$ be related to the maximum clique sizes of $$G'$$ and $$G''$$? In the case that $$G$$ is infinite, is it even clear that maximum clique size of $$G$$ and $$G'$$ both finite implies that the maximum clique size of $$G$$ is finite?

I'm guessing that in complete generality probably little can be said, because a clique of $$G$$ need not a priori respect the clique structures of $$G'$$ and $$G''$$. But in my setting, I have a particular pair of graphs $$G', G''$$ that I know a little bit about- both are infinite and locally infinite, both have finite maximum cliques (and I know these sizes explicitly), both have finite chromatic number, they're bi-lipschitz equivalent to each other, etc. So I'd also be happy with results that assume extra structure (but not finiteness) on $$G,G',G''$$.

Thanks for reading; any ideas would be greatly appreciated.

This is a rather general question, and I am certainly not in a position to give an exhaustive answer - but here. at least, is an answer to your particular question as to whether the clique sizes of $G'$ and $G''$ being finite implies that the clique size of $G$ is finite. So, the answer is yes -- by the basic Ramsey's theorem. If you had arbitrarily large cliques in $G$, then you could partition the edges of arbitrarily large complete graph into two sets with the clique sizes of the subgraphs induced by these sets being bounded, in a direct contradiction with the aforementioned theorem.
• basil, Ramsey's theorem will also give you reasonable bounds on the clique number of $G$. If the clique numbers of $G'$ and $G''$ are $r$ and $s$, then the clique number of $G$ must be less than $R(r+1, s+1) \leq \binom {r+s} r$. Jul 24 '13 at 11:26
Let $B$ and $R$ be two simple graphs with vertex set $V$, and let $G(B,R)$ be the simple graph with vertex set $V$, in which two vertices are adjacent if they are adjacent in at least one of $B$ and $R$. For $X \subseteq V$, we denote by $B|X$ the subgraph of $B$ induced by $X$; let $R|X$ and $G(B,R)|X$ be defined similarly. We say that the pair $(B,R)$ is additive if for every $X \subseteq V$, the sum of the clique numbers of $B|X$ and $R|X$ is at least the clique number of $G(B,R)|X$. In this paper we give a necessary and sufficient characterization of additive pairs of graphs. This is a numerical variant of a structural question studied in $[1]$.