On ramsey numbers of forests versus nearly complete graphs

A formula is presented for the ramsey number of any forest of order at least 3 versus any graph G of order n ≥ 4 having clique number n - 1. In particular, if T is a tree of order m ≥ 3, then r(T, G) = 1 + (m - 1)(n - 2).     

Irredundant ramsey numbers for graphs

The irredundant Ramsey number s(m, n) is the least value of p such that for any p-vertex graph G, either G has an irredundant set of at least n vertices or its complement G has an irredundant set of at least m vertices. The existence of these numbers is guaranteed by Ramsey's theorem. We prove that s(3, 3) = 6, s(3, 4) = 8, and s(3,5) = 12.     

Size ramsey numbers of stars versus 4‐chromatic graphs

We investigate the asymptotics of the size Ramsey number î(K_1,nF), where K_1,n is the n‐star and F is a fixed graph. The author 11 has recently proved that r?(K_1,n,F)=(1+o(1))n² for any F with chromatic number χ(F)=3. Here we show that r?(K_1,n,F)≤ n²+o(n²), if χ (F) ≥ 4 and conjecture that this is sharp. We prove the case χ(F)=4 of the conjecture, that is, that r?(K_1,n,F)=(4+o(1))n² for any 4‐chromatic graph F. Also, some general lower bounds are obtained. © 2003 Wiley Periodicals, Inc. J Graph Theory 42: 220–233, 2003     

On ramsey numbers for large disjoint unions of graphs

Let be a fixed finite set of connected graphs. Results are given which, in principle, permit the Ramsey number r(G, H) to be evaluated exactly when G and H are sufficiently large disjoint unions of graphs taken from . Such evaluations are often possible in practice, as shown by several examples. For instance, when m and n are large, and mn,

r(mK_k, nK_l)=(k − 1)m+ln+r(K_k−1, K_l−1)−2.

     

All triangle-graph ramsey numbers for connected graphs of order six

The Ramsey numbers r(K_3′ G) are determined for all connected graphs G of order six.     

Sparse ramsey graphs

IfH is a Ramsey graph for a graphG thenH is rich in copies of the graphG. Here we prove theorems in the opposite direction. We find examples ofH such that copies ofG do not form short cycles inH. This provides a strenghtening also, of the following well-known result of Erdős: there exist graphs with high chromatic number and no short cycles. In particular, we solve a problem of J. Spencer. Dedicated to Paul Erdős on his seventieth birthday     

Chromatic numbers of hypergraphs and coverings of graphs

Burr recently proved [3] that for positive integers m₁, m₂……m_k, and any graph G we have X(G) if and only if G can be expressed as the edge disjoint union of subgraphs F_i satisfying X(F_i) ≤ m_i. This theorem is generalized to hypergraphs. By suitable interpretations the generalization is then used to deduce propositions on coverings of graphs.     

A class of self-complementary graphs and lower bounds of some ramsey numbers

A method is described of constructing a class of self-complementary graphs, that includes a self-complementary graph, containing no K₅, with 41 vertices and a self-complementary graph, containing no K₇, with 113 vertices. The latter construction gives the improved Ramsey number lower bound r(7, 7) ≥ 114.     

Some small ramsey numbers

In previous work, the Ramsey numbers have been evaluated for all pairs of graphs with at most four points. In the present note, Ramsey numbers are tabulated for pairs F₁, F₂ of graphs where F₁ has at most four points and F₂ has exactly five points. Exact results are listed for almost all of these pairs.     

Tree-complete graph ramsey numbers

The ramsey number of any tree of order m and the complete graph of order n is 1 + (m ? 1)(n ? 1).     

Some connected ramsey numbers

A graph G is co-connected if both G and its complement ? are connected and nontrivial. For two graphs A and B, the connected Ramsey number r_c(A, B) is the smallest integer n such that there exists a co-connected graph of order n, and if G is a co-connected graph on at least n vertices, then A ? G or B ? ?. If neither A or B contains a bridge, then it is known that r_c(A, B) = r(A, B), where r(A, B) denotes the usual Ramsey number of A and B. In this paper r_c(A, B) is calculated for some pairs (A, B) when r(A, B) is known and at least one of the graphs A or B has a bridge. In particular, r_c(A, B) is calculated for A a path and B either a cycle, star, or complete graph, and for A a star and B a complete graph.     

Chromatic numbers of layered graphs with a bounded maximal clique

A graph is called n-layered if the set of its vertices is a union of pairwise nonintersecting n-cliques. We estimatechromatic numbers of n-layered graphs without (n + 1)-cliques. Bibliography: 10 titles.     

On ramsey numbers for books

For n = 1, 2, …, let B_n = K₂ + K?_n. We pose the problem of determining the Ramsey numbers r(B_m, B_n) and demonstrate that in many cases critical colorings are avialable from known examples of strongly regular graphs.     

Lower bounds for small diagonal ramsey numbers

Let p = 4r + 1 be a prime. Let G be the graph on the p points 0, 1,…, p−1 formed by connecting two points with an edge iff their difference is a quadratic residue mod p. Let k be the size of the largest clique contained in G. Then it is well known that the diagonal Ramsey number R₂(k + 1) > p. We show R₂(k + 2) > 2p + 2. We also compute k for all p < 3000.