On Ramsey numbers of fans

It is shown that r(F₂,F_n)=4n+1 for n≥2, and r(F_s,F_n)≤4n+2s for n≥s≥2.     

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.     

Size Ramsey numbers of stars versus cliques

The size Ramsey number of two graphs and is the smallest integer such that there exists a graph on edges with the property that every red-blue colouring of the edges of yields a red copy of or a blue copy of . In 1981, Erdős observed that and he conjectured that this upper bound on is sharp. In 1983, Faudree and Sheehan extended this conjecture as follows: They proved the case . In 2001, Pikhurko showed that this conjecture is not true for and , by disproving the mentioned conjecture of Erdős. Here, we prove Faudree and Sheehan's conjecture for a given and .     

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₇.     

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₄).     

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₂.     

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$.     

List Ramsey numbers

We introduce a list‐coloring extension of classical Ramsey numbers. We investigate when the two Ramsey numbers are equal, and in general, how far apart they can be from each other. We find graph sequences where the two are equal and where they are far apart. For $?$‐uniform cliques we prove that the list Ramsey number is bounded by an exponential function, while it is well known that the Ramsey number is superexponential for uniformity at least 3. This is in great contrast to the graph case where we cannot even decide the question of equality for cliques.     

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     

Book Ramsey numbers. I

A book B_p is a graph consisting of p triangles sharing a common edge. In this paper we prove that if p ≤ q/6 ?o(q) and q is large, then the Ramsey number r (B_p,B_q) is given by r (B_p,B_q) = 2q+3, and the constant 1/6 is essentially best possible. Our proof is based on Szemerédi's uniformity lemma and a stability result for books. © 2005 Wiley Periodicals, Inc. Random Struct. Alg., 2005     

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.     

Star-critical Ramsey numbers for large generalized fans and books

In this paper, we show that for any fixed integers $m\ge 2$ and $t\ge 2$, the star-critical Ramsey number $r_1(K_1+n{K}_t,K_{m+1})=(m?1)tn+t$ for all sufficiently large $n$. Furthermore, for any fixed integers $p\ge 2$ and $m\ge 2$, $r_1(K_p+n{K}_1,K_{m+1})=(m?1+o\left(1\right))n$ as $n\to \infty$.     

The tail is cut for Ramsey numbers of cubes

The Ramsey number R(G) of a graph G is the least integer p such that for all bicolorings of the edges of the complete graph K_p, one of the monochromatic subgraphs contains a copy of G. We show that for any positive constant c and bipartite graph G=(U,V;E) of order n where the maximum degree of vertices in U is at most , . Moreover, we show that the Ramsey number of the cube Q_n of dimension n satisfies . In both cases, the small terms are removed from the powers in the upper bounds of a earlier result of the author.     

The Ramsey number of paths with respect to wheels

For graphs G and H, the Ramsey numberR(G,H) is the smallest positive integer n such that every graph F of order n contains G or the complement of F contains H. For the path P_n and the wheel W_m, it is proved that R(P_n,W_m)=2n-1 if m is even, m?4, and n?(m/2)(m-2), and R(P_n,W_m)=3n-2 if m is odd, m?5, and n?(m-1/2)(m-3).     

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.

     

New upper bound formulas with parameters for Ramsey numbers

In this paper, we obtain some new results R(5,12)?848, R(5,14)?1461, etc., and we obtain new upper bound formulas for Ramsey numbers with parameters.     

Some geometric structures and bounds for Ramsey numbers

We investigate several bounds for both K_2,m−K_1,n Ramsey numbers and K_2,m−K_1,n bipartite Ramsey numbers, extending some previous results. Constructions based on certain geometric structures (designs, projective planes, unitals) yield classes of near-optimal bounds or even exact values. Moreover, relationships between these numbers are also discussed.