Cliques in the union of \(C_4\)-free graphs (Q2413627)

A graph \(G\) is \(C_4\)-free if no induced subgraph of \(G\) is isomorphic to the \(4\)-cycle. The authors prove that if \(G\) is a complete graph with vertex set \(V\) that is the union of two \(C_4\)-free graphs \(B\) and \(R\) with the same vertex set, then \(V(G) = X\cup Y\cup Z\) where \(X\) and \(Z\) are cliques in \(B\), and \(Y\) and \(Z\) are cliques in \(R\). This implies the following inequality relating the clique numbers of these three graphs: \(|V| = \omega(G)\le \omega(B)+\omega(R)\). For general \(C_4\)-free graphs \(B\) and \(R\), the following bounds are proved: \newline \(\omega(B\cup R)\le \omega(B)+\omega(R)+\frac{1}{2}\min\{\omega(B),\omega(R)\}\) and \(\omega(B\cup R)\le \omega(B)+\omega(R)+\omega(B\cap R)\). The motivation for this study comes from Ramsey theory, or, more precisely, from the quest of identifying conditions on pairs of graphs \(B\) and \(R\) such that every clique in \(B\cup R\) is the union of a clique in \(B\) and a clique in \(R\). The results in this paper generalize a result of \textit{A. Gyárfás} and \textit{J. Lehel} [Electron. J. Comb. 23, No. 3, Research Paper P3.40, 5 p. (2016; Zbl 1344.05106)] showing that if the edges of a complete graph \(G\) are colored with red and blue (both colors can appear on an edge) so that there is no monochromatic induced \(C_4\) and there is no \(K_5\) on which both color classes induce a \(C_5\), then the vertices of \(G\) can be partitioned into a red clique and a blue clique.