Welcome to the new version of CaltechAUTHORS. Login is currently restricted to library staff. If you notice any issues, please email coda@library.caltech.edu
Published September 2015 | public
Journal Article Open

Cliques in the union of graphs


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.

Additional Information

© 2015 Elsevier Inc. Received 19 November 2012; Available online 21 April 2015. The research of the first author was supported by BSF grant No. 2006099 and by the Discount Bank Chair at the Technion. The research of the second author was supported by BSF grant No. 2006099. The research of the third author was supported by BSF grant No. 2006099, and National Science Foundation grants DMS-1001091 and IIS-1117631. We would like to thank Irena Penev for her careful reading of an early version of this manuscript, and for her helpful suggestions regarding its presentation.

Attached Files

Submitted - edgeunion.pdf


Files (313.3 kB)
Name Size Download all
313.3 kB Preview Download

Additional details

August 22, 2023
August 22, 2023