Cliques in the union of graphs

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 Band 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 C_4 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.

Files

Additional details