Cliques in the union of C₄-free graphs

DOI10.1007/S00373-018-1898-4zbMATH Open1430.05090arXiv1511.08772OpenAlexW2963559438MaRDI QIDQ2413627FDOQ2413627

Authors: Abeer Othman, Eli Berger 

Publication date: 14 September 2018

Published in: Graphs and Combinatorics (Search for Journal in Brave)

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=XcupYcupZ$. Further, if $xinZ$ 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))leqomega(B)+omega(R)+frac12min(omega(B),omega(R))$ and $omega(G(B,R))leqomega(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$.

Full work available at URL: https://arxiv.org/abs/1511.08772

Recommendations

• Colorings generated by monotone properties
• Complete critical Ramsey numbers of cycle and \({K_4}\) numbers
• scientific article; zbMATH DE number 1161351
• An extremal problem on v-partite graphs
• Ramsey numbers of connected clique matchings
• Stability and Ramsey numbers for cycles and wheels
• Partitioning Two-Coloured Complete Graphs into Two Monochromatic Cycles
• Large cliques in \(C_4\)-free graphs
• scientific article; zbMATH DE number 1743977

zbMATH Keywords

clique\(C_4\)-free graphobedient set

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Ramsey theory (05D10)

Cites Work

• Cliques in the union of graphs
• KKM -- a topological approach for trees

Cited In (4)

• Large cliques in \(C_4\)-free graphs
• Cliques in the union of graphs
• Title not available (Why is that?)
• Cliques in \(C_4\)-free graphs of large minimum degree

This page was built for publication: Cliques in the union of \(C_4\)-free graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2413627)