The Ramsey numbers for disjoint unions of trees

For given graphs G and H, the Ramsey numberR(G,H) is the smallest natural number n such that for every graph F of order n: either F contains G or the complement of F contains H. In this paper, we investigate the Ramsey number R(∪G,H), where G is a tree and H is a wheel W_m or a complete graph K_m. We show that if n?3, then R(kS_n,W₄)=(k+1)n for k?2, even n and R(kS_n,W₄)=(k+1)n-1 for k?1 and odd n. We also show that .     

On three color Ramsey numbers R(C4,C4,K1,n)

For $k$ given graphs $G_1,G_2,\dots ,G_k$, $k\ge 2$, the $k$-color Ramsey number, denoted by $R(G_1,G_2,\dots ,G_k)$, is the smallest integer $N$ such that if we arbitrarily color the edges of a complete graph of order $N$ with $k$ colors, then it always contains a monochromatic copy of $G_i$ colored with $i$, for some $1\le i\le k$. Let $C_m$ be a cycle of length $m$ and $K_{1,n}$ a star of order $n+1$. In this paper, firstly we give a general upper bound of $R(C_4,C_4,\dots ,C_4,K_{1,n})$. In particular, for the 3-color case, we have $R(C_4,C_4,K_{1,n})\le n+?\sqrt{4n+5}?+3$ and this bound is tight in some sense. Furthermore, we prove that $R(C_4,C_4,K_{1,n})\le n+?\sqrt{4n+5}?+2$ for all $n={?}^2??$ and $?\ge 2$, and if $?$ is a prime power, then the equality holds.     

Lower bounds for multicolor classical Ramsey numbers

A method is put forward to establish the lower bounds for somen-color classical Ramsey numbers . With this method six new explicit lower boundsR ₄(4) ≥458,R ₃(5) ≥ 242,R ₃(6)≥1070,R ₃(7) ≥ 1214,R ₃(8) ≥2834 andR ₃(9) ≥ 5282 are obtained using a computer. Project supported by Guangxi Natural Science Foundation     

Some properties of Ramsey numbers

In this paper, some properties of Ramsey numbers are studied, and the following results are presented.

1. (1) For any positive integers k₁, k₂, …, k_m l₁, l₂, …, l_m (m> 1), we have

.

2. (2) For any positive integers k₁, k₂, …, k_m, l₁, l₂, …, l_n , we have

. Based on the known results of Ramsey numbers, some results of upper bounds and lower bounds of Ramsey numbers can be directly derived by those properties.

     

Star-critical Ramsey numbers

The graph Ramsey numberR(G,H) is the smallest integer r such that every 2-coloring of the edges of K_r contains either a red copy of G or a blue copy of H. We find the largest star that can be removed from K_r such that the underlying graph is still forced to have a red G or a blue H. Thus, we introduce the star-critical Ramsey numberr_∗(G,H) as the smallest integer k such that every 2-coloring of the edges of K_r−K_1,r−1−k contains either a red copy of G or a blue copy of H. We find the star-critical Ramsey number for trees versus complete graphs, multiple copies of K₂ and K₃, and paths versus a 4-cycle. In addition to finding the star-critical Ramsey numbers, the critical graphs are classified for R(T_n,K_m), R(nK₂,mK₂) and R(P_n,C₄).     

The Ramsey numbers of paths versus wheels

For two given graphs G₁ and G₂, the Ramsey number R(G₁,G₂) is the smallest integer n such that for any graph G of order n, either G contains G₁ or the complement of G contains G₂. Let P_n denote a path of order n and W_m a wheel of order m+1. In this paper, we show that R(P_n,W_m)=2n-1 for m even and n?m-1?3 and R(P_n,W_m)=3n-2 for m odd and n?m-1?2.     

The Ramsey numbers for cycles versus wheels of odd order

For two given graphs G₁ and G₂, the Ramsey number R(G₁,G₂) is the smallest integer n such that for any graph G of order n, either G contains G₁ or the complement of G contains G₂. Let C_n denote a cycle of order n and W_m a wheel of order m+1. It is conjectured by Surahmat, E.T. Baskoro and I. Tomescu that R(C_n,W_m)=2n−1 for even m≥4, n≥m and (n,m)≠(4,4). In this paper, we confirm the conjecture for n≥3m/2+1.     

Size Ramsey numbers for some regular graphs

P. Erdös, R.J. Faudree, C.C. Rousseau and R.H. Schelp [P. Erdös, R.J. Faudree, C.C. Rousseau, R.H. Schelp, The size Ramsey number, Period. Math. Hungar. 9 (1978) 145-161] studied the asymptotic behaviour of for certain graphs G,H. In this paper there will be given a lower bound for the diagonal size Ramsey number of K_n,n,n. The result is a generalization of a theorem for K_n,n given by P. Erdös and C.C. Rousseau [P. Erdös, C.C. Rousseau, The size Ramsey numbers of a complete bipartite graph, Discrete Math. 113 (1993) 259-262].Moreover, an open question for bounds for size Ramsey number of each n-regular graph of order n+t for t>n−1 is posed.     

Size bipartite Ramsey numbers

Let B, B₁ and B₂ be bipartite graphs, and let B→(B₁,B₂) signify that any red-blue edge-coloring of B contains either a red B₁ or a blue B₂. The size bipartite Ramsey number is defined as the minimum number of edges of a bipartite graph B such that B→(B₁,B₂). It is shown that is linear on n with m fixed, and is between c₁n²2ⁿ and c₂n³2ⁿ for some positive constants c₁ and c₂.     

ContributionsChromatic Ramsey numbers

Suppose G is a graph. The chromatic Ramsey number r_c(G) of G is the least integer m such that there exists a graph F of chromatic number m for which the following is true: for any 2-colouring of the edges of F there is a monochromatic subgraph isomorphic to G. Let M_n = min[r_c(G): χ(G) = n]. It was conjectured by Burr et al. (1976) that M_n = (n − 1)² + 1. This conjecture has been confirmed previously for n 4. In this paper, we shall prove that the conjecture is true for n = 5. We shall also improve the upper bounds for M₆ and M₇.     

Linear Ramsey numbers of sparse graphs

The Ramsey number R(G₁,G₂) of two graphs G₁ and G₂ is the least integer p so that either a graph G of order p contains a copy of G₁ or its complement G^c contains a copy of G₂. In 1973, Burr and Erd?s offered a total of $25 for settling the conjecture that there is a constant c = c(d) so that R(G,G)≤ c|V(G)| for all d‐degenerate graphs G, i.e., the Ramsey numbers grow linearly for d‐degenerate graphs. We show in this paper that the Ramsey numbers grow linearly for degenerate graphs versus some sparser graphs, arrangeable graphs, and crowns for example. This implies that the Ramsey numbers grow linearly for degenerate graphs versus graphs with bounded maximum degree, planar graphs, or graphs without containing any topological minor of a fixed clique, etc. © 2005 Wiley Periodicals, Inc. J Graph Theory     

Some multicolor bipartite Ramsey numbers involving cycles and a small number of colors

For bipartite graphs $G_1,G_2,\dots ,G_k$, the bipartite Ramsey number $b(G_1,G_2,\dots ,G_k)$ is the least positive integer $b$ so that any coloring of the edges of $K_{b,b}$ with $k$ colors will result in a copy of $G_i$ in the $i$th color for some $i$. In this paper, our main focus will be to bound the following numbers: $b(C_{2t_1},C_{2t_2})$ and $b(C_{2t_1},C_{2t_2},C_{2t_3})$ for all $t_i\ge 3,$$b(C_{2t_1},C_{2t_2},C_{2t_3},C_{2t_4})$ for $3\le t_i\le 9,$ and $b(C_{2t_1},C_{2t_2},C_{2t_3},C_{2t_4},C_{2t_5})$ for $3\le t_i\le 5.$ Furthermore, we will also show that these mentioned bounds are generally better than the bounds obtained by using the best known Zarankiewicz-type result.     

Configurations in projective planes and quadrilateral-star Ramsey numbers

Some classes of configurations in projective planes with polarity are constructed. As the main result, lower bounds for the Ramsey numbers r(n)=r(C₄;K_1,n) are derived from these geometric structures, which improve some bounds due to Parsons about 30 years ago, and also yield a new class of optimal values: r(q²-2q+1)=q²-q+1 whenever q is a power of 2. Moreover, the constructions also imply a known result on C₄-K_1,n bipartite Ramsey numbers.     

Degree Ramsey numbers for even cycles

Let $H\stackrel{s}{?}G$ denote that any $s$-coloring of $E\left(H\right)$ contains a monochromatic $G$. The degree Ramsey number of a graph $G$, denoted by $R_{\Delta }(G,s)$, is $min\{\Delta \left(H\right):H\stackrel{s}{?}G\}$. We consider degree Ramsey numbers where $G$ is a fixed even cycle. Kinnersley, Milans, and West showed that $R_{\Delta }(C_{2k},s)\ge 2s$, and Kang and Perarnau showed that $R_{\Delta }(C_4,s)=\Theta \left(s^2\right)$. Our main result is that $R_{\Delta }(C_6,s)=\Theta \left(s^{3∕2}\right)$ and $R_{\Delta }(C_{10},s)=\Theta \left(s^{5∕4}\right)$. Additionally, we substantially improve the lower bound for $R_{\Delta }(C_{2k},s)$ for general $k$.     

New Lower Bounds on the Multicolor Ramsey Numbers R r (C 2 m )

The multicolor Ramsey number R_r(H) is defined to be the smallest integer n=n(r) with the property that any r-coloring of the edges of the complete graph K_n must result in a monochromatic subgraph of K_n isomorphic to H. It is well known that 2^rm<R_r(C_2m+1)<2(r+2)!m and R_r(C_2m)≥(r−1)(m−1)+1. In this paper, we prove that R_r(C_2m)≥2(r−1)(m−1)+2. This research is supported by NSFC(60373096, 60573022) and SRFDP(20030141003)