Cliques in the union of $C_4$-free graphs

Abstract

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$. We prove that if $B$ and $R$ are two $C_4$-free graphs on the same vertex set $V$ and $G(B,R)$ is the complete graph, then there exists an $B$-clique $X$, an $R$-clique $Y$ and a clique $Z$ in $B$ and $R$, such that $V=X\cup Y\cup Z$. Further, if $x\in Z$ then $x$ is one of the vertices of some double $C_5$ in $G(B,R)$. In particular, if also $G(B,R)$ does not contains a double $C_5$, then $V$ is obedient. We obtain that if $B$ and $R$ are $C_4$-free graphs then $\omega (G(B,R))\le \omega (B)+\omega (R)+\frac{1}{2}\min (\omega (B),\omega (R))$ and $\omega (G(B,R))\le \omega (B)+\omega (R)+\omega (H(B,R))$ where $H(B,R)$ is the simple graph with vertex set $V$, in which two vertices are adjacent if they are adjacent in $B$ and $R$.