Cliques in the union of $C_4$-free 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$. 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 $ω(G(B,R))\leq ω(B)+ω(R)+\frac{1}{2}\min(ω(B),ω(R))$ and $ω(G(B,R))\leq ω(B)+ω(R)+ω(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$.

No reviews yet.

No comments yet.