Cliques in the union of graphs

Ron Aharoni, Eli Berger, Maria Chudnovsky, Juba Ziani

Research output: Contribution to journalArticlepeer-review

2 Scopus citations

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. For X⊆V, we denote by B|X the subgraph of B induced by X; let R|X and G(B, R)|X be defined similarly. A clique in a graph is a set of pairwise adjacent vertices. A subset U⊆V is obedient if U is the union of a clique of B and a clique of R. Our first result is that if B has no induced cycles of length four, and R has no induced cycles of length four or five, then every clique of G(B, R) is obedient. This strengthens a previous result of the second author, stating the same when B has no induced C4 and R is chordal.The clique number of a graph is the size of its maximum clique. We say that the pair (. B, R) is additive if for every X⊆. V, the sum of the clique numbers of B|. X and R|. X is at least the clique number of G(. B, R)|. X. Our second result is a sufficient condition for additivity of pairs of graphs.

Original languageEnglish (US)
Pages (from-to)170-186
Number of pages17
JournalJournal of Combinatorial Theory. Series B
Volume114
DOIs
StatePublished - Sep 1 2015
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics
  • Computational Theory and Mathematics

Keywords

  • Chordal graphs
  • Cliques

Fingerprint

Dive into the research topics of 'Cliques in the union of graphs'. Together they form a unique fingerprint.

Cite this