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 language | English (US) |
---|---|
Pages (from-to) | 170-186 |
Number of pages | 17 |
Journal | Journal of Combinatorial Theory. Series B |
Volume | 114 |
DOIs | |
State | Published - Sep 1 2015 |
Externally published | Yes |
All Science Journal Classification (ASJC) codes
- Theoretical Computer Science
- Discrete Mathematics and Combinatorics
- Computational Theory and Mathematics
Keywords
- Chordal graphs
- Cliques