pith. sign in

arxiv: 1511.08772 · v1 · pith:3CESDXHVnew · submitted 2015-11-27 · 🧮 math.CO

Cliques in the union of C₄-free graphs

classification 🧮 math.CO
keywords omegaadjacentgraphsthenvertexcliquefreegraph
0
0 comments X
read the original 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))\leq \omega(B)+\omega(R)+\frac{1}{2}\min(\omega(B),\omega(R))$ and $\omega(G(B,R))\leq \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$.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.