Cliques in the union of C₄-free graphs

DOI10.1007/S00373-018-1898-4MaRDI QIDQ2413627zbMATH OpenOpenAlexFDO

Authors Abeer Othman, Eli Berger

Publication date 14 September 2018

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

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

zbMATH Keywords

\(C_4\)-free graph clique obedient set

Mathematics Subject Classification ID

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

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 c u p Y c u p Z

. Further, if

x i n 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

o m e g a (G (B, R)) l e q o m e g a (B) + o m e g a (R) + f r a c 12 m i n (o m e g a (B), o m e g a (R))

and

o m e g a (G (B, R)) l e q o m e g a (B) + o m e g a (R) + o m e g a (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

.

Review text

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.

Recommendations

Cites work

Cited in

(5)

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)