Cliques in the Union of C4-Free Graphs

被引：0

作者：

Othman, Abeer ^{[1
]}

Berger, Eli ^{[1
]}

机构：

[1] Univ Haifa, Dept Math, IL-31905 Haifa, Israel

来源：

GRAPHS AND COMBINATORICS | 2018年 / 34卷 / 04期

基金：

以色列科学基金会; 美国国家科学基金会;

关键词：

C-4-free graphs; Cliques; Obedient sets;

D O I：

10.1007/s00373-018-1898-4

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

Let B and R be two simple C-4-free graphs with the same vertex set V, and let B. R be the simple graph with vertex set V and edge set E(B). E(R). We prove that if B. R is a complete graph, then there exists a B-clique X, an R-clique Y and a set Z which is a clique both in B and in R, such that V = X. Y. Z. For general B and R, not necessarily forming together a complete graph, we obtain that omega(B boolean OR R) <= omega(B) + omega(R) + 1/2 min(omega(B), omega(R)) and omega(B boolean OR R) <= omega(B) + omega(R) + omega(B boolean AND R) where B boolean AND R is the simple graph with vertex set V and edge set E(B) boolean AND E(R).

引用

页码：607 / 612

页数：6