Tripartite Ramsey numbers for paths

In this article, we study the tripartite Ramsey numbers of paths. We show that in any two‐coloring of the edges of the complete tripartite graph K(n, n, n) there is a monochromatic path of length (1 ? o(1))2n. Since R(P_2n+1,P_2n+1)=3n, this means that the length of the longest monochromatic path is about the same when two‐colorings of K_3n and K(n, n, n) are considered. © 2007 Wiley Periodicals, Inc. J Graph Theory 55: 164–174, 2007     

Multipartite Ramsey numbers for odd cycles

In this paper we study multipartite Ramsey numbers for odd cycles. We formulate the following conjecture: Let n≥5 be an arbitrary positive odd integer; then, in any two‐coloring of the edges of the complete 5‐partite graph K((n?1)/2, (n?1)/2, (n?1)/2, (n?1)/2, 1) there is a monochromatic C_n, a cycle of length n. This roughly says that the Ramsey number for C_n (i.e. 2n?1 ) will not change (somewhat surprisingly) if four large “holes” are allowed. Note that this would be best possible as the statement is not true if we delete from K_2n?1 the edges within a set of size (n+ 1)/2. We prove an approximate version of the above conjecture. © 2009 Wiley Periodicals, Inc. J Graph Theory 61:12‐21, 2009     

A constructive approach for the lower bounds on the Ramsey numbers R (s,t)

Graph G is a (k, p)‐graph if G does not contain a complete graph on k vertices K_k, 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 K_k?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     

On graphs with small Ramsey numbers*

Let R(G) denote the minimum integer N such that for every bicoloring of the edges of K_N, at least one of the monochromatic subgraphs contains G as a subgraph. We show that for every positive integer d and each γ,0 < γ < 1, there exists k = k(d,γ) such that for every bipartite graph G = (W,U;E) with the maximum degree of vertices in W at most d and , . This answers a question of Trotter. We give also a weaker bound on the Ramsey numbers of graphs whose set of vertices of degree at least d + 1 is independent. © 2001 John Wiley & Sons, Inc. J Graph Theory 37: 198–204, 2001     

Upper bounds for Ramsey numbers

The Ramsey number R(G₁,G₂,…,G_k) is the least integer p so that for any k-edge coloring of the complete graph K_p, there is a monochromatic copy of G_i of color i. In this paper, we derive upper bounds of R(G₁,G₂,…,G_k) for certain graphs G_i. In particular, these bounds show that R(9,9)6588 and R(10,10)23556 improving the previous best bounds of 6625 and 23854.     

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

Asymptotic bounds for some bipartite graph: complete graph Ramsey numbers

The Ramsey number r(H,K_n) is the smallest integer N so that each graph on N vertices that fails to contain H as a subgraph has independence number at least n. It is shown that r(K_2,m,K_n)(m−1+o(1))(n/log n)² and r(C_2m,K_n)c(n/log n)^m/(m−1) for m fixed and n→∞. Also r(K_2,n,K_n)=Θ(n³/log² n) and .     

Gallai–Ramsey numbers for cycles

For given graphs G and H and an integer k, the Gallai–Ramsey number is defined to be the minimum integer n such that, in any k coloring of the edges of K_n, there exists a subgraph isomorphic to either a rainbow coloring of G or a monochromatic coloring of H. In this work, we consider Gallai–Ramsey numbers for the case when G=K₃ and H is a cycle of a fixed length.     

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.     

A note on the monotonicity of mixed Ramsey numbers

For two graphs, G and H, an edge coloring of a complete graph is (G,H)-good if there is no monochromatic subgraph isomorphic to G and no rainbow subgraph isomorphic to H in this coloring. The set of numbers of colors used by (G,H)-good colorings of K_n is called a mixed Ramsey spectrum. This note addresses a fundamental question of whether the spectrum is an interval. It is shown that the answer is “yes” if G is not a star and H does not contain a pendant edge.     

3-Color bipartite Ramsey number of cycles and paths

The -color bipartite Ramsey number of a bipartite graph is the least integer for which every -edge-colored complete bipartite graph contains a monochromatic copy of . The study of bipartite Ramsey numbers was initiated, over 40 years ago, by Faudree and Schelp and, independently, by Gyárfás and Lehel, who determined the 2-color Ramsey number of paths. In this paper we determine asymptotically the 3-color bipartite Ramsey number of paths and (even) cycles.     

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

On Ramsey numbers of uniform hypergraphs with given maximum degree

For every ?>0 and every positive integers Δ and r, there exists C=C(?,Δ,r) such that the Ramsey number, R(H,H) of any r-uniform hypergraph H with maximum degree at most Δ is at most C|V(H)|^1+?.     

CO‐irredundant Ramsey numbers for graphs

The study of the CO‐irredundant Ramsey numbers t(n₁, ···, n_k) is initiated. It is shown that several values and bounds for these numbers may be obtained from the well‐studied generalized graph Ramsey numbers and the values of t(4, 5), t(4, 6) and t(3, 3, m) are calculated. © 2000 John Wiley & Sons, Inc. J Graph Theory 34: 258–268, 2000     

Mean Ramsey–Turán numbers

A ρ‐mean coloring of a graph is a coloring of the edges such that the average number of colors incident with each vertex is at most ρ. For a graph H and for ρ ≥ 1, the mean Ramsey–Turán number RT(n, H,ρ ? mean) is the maximum number of edges a ρ‐mean colored graph with n vertices can have under the condition it does not have a monochromatic copy of H. It is conjectured that where is the maximum number of edges a k edge‐colored graph with n vertices can have under the condition it does not have a monochromatic copy of H. We prove the conjecture holds for . We also prove that . This result is tight for graphs H whose clique number equals their chromatic number. In particular, we get that if H is a 3‐chromatic graph having a triangle then . © 2006 Wiley Periodicals, Inc. J Graph Theory 53: 126–134, 2006     

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.     

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.     

On Generalized Ramsey Numbers for 3‐Uniform Hypergraphs

The well‐known Ramsey number is the smallest integer n such that every ‐free graph of order n contains an independent set of size u. In other words, it contains a subset of u vertices with no K₂. Erd?s and Rogers introduced a more general problem replacing K₂ by  for . Extending the problem of determining Ramsey numbers they defined the numbers where the minimum is taken over all ‐free graphs G of order n. In this note, we study an analogous function for 3‐uniform hypergraphs. In particular, we show that there are constants c₁ and c₂ depending only on s such that