3
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ thank you for your response- it seems Ramsey's theorem works quite well to answer the finiteness question. $\endgroup$ Jul 23 '13 at 21:22
  • $\begingroup$ 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$. $\endgroup$
    – Ben Barber
    Jul 24 '13 at 11:26
1
$\begingroup$

Maria Chudnovsky and Juba Ziani have an arXiv paper up today in which they say something about this problem for finite graphs.

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

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