Name
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 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. |
Year | DOI | Venue |
|---|---|---|
2015 | 10.1016/j.jctb.2015.04.004 | Journal of Combinatorial Theory, Series B |
Keywords | Field | DocType |
Chordal graphs,Cliques | Graph,Discrete mathematics,Additive function,Combinatorics,Clique,Vertex (geometry),Chordal graph,Clique-sum,Independent set,Mathematics,Split graph | Journal |
Volume | Issue | ISSN |
114 | C | 0095-8956 |
Citations | PageRank | References |
1 | 0.43 | 2 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Ron Aharoni I | 1 | 13 | 8.92 |
| Eli Berger | 2 | 182 | 52.72 |
| Maria Chudnovsky | 3 | 390 | 46.13 |
| Juba Ziani | 4 | 29 | 5.77 |