Name
Abstract | ||
|---|---|---|
Graph G is a (k, p)-graph if G does not contain a complete graph on k vertices Kk, nor an independent set of order p. Given a (k, p)-graph G and a (k, q)-graph H, such that G and H contain an induced subgraph isomorphic to some Kk-1-free graph M, we construct a (k, p + q - 1)-graph on n(G) + n(H) + n(M) vertices. This implies that R (k, p + q - 1) ≥ R (k, p) + R (k, q) + n(M) - 1, where R (s, t) is the classical two-color Ramsey number. By applying this construction, and some its generalizations, we improve on 22 lower bounds for R (s, t), for various specific values of s and t. In particular, we obtain the following new lower bounds: R (4, 15) ≥ 153, R (6, 7) ≥ 111, R (6, 11) ≥ 253, R (7, 12) ≥ 416, and R (8, 13) ≥ 635. Most of the results did not require any use of computer algorithms. © 2004 Wiley Periodicals, Inc. J Graph Theory 47: 231–239, 2004 |
Year | DOI | Venue |
|---|---|---|
2004 | 10.1002/jgt.v47:3 | Journal of Graph Theory |
Keywords | Field | DocType |
lower bound,independent set,complete graph,ramsey numbers,ramsey number,graph coloring | Graph theory,Discrete mathematics,Complete graph,Combinatorics,Vertex (geometry),Induced subgraph,Ramsey's theorem,Independent set,Isomorphism,Mathematics,Graph coloring | Journal |
Volume | Issue | ISSN |
47 | 3 | 0364-9024 |
Citations | PageRank | References |
7 | 0.88 | 3 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Xiaodong Xu | 1 | 26 | 9.91 |
| Xie Zheng | 2 | 15 | 1.83 |
| Stanislaw P. Radziszowski | 3 | 108 | 23.90 |