Articles
Discrete Applied Mathematics (0166218X)378pp. 87-92
Given two graphs H and G, the size multipartite Ramsey number mj(H,G) is the smallest natural number t such that an arbitrary coloring of the edges of Kj×t, a complete multipartite graph whose vertex set is partitioned into j parts each of size t, using two colors (red and blue), necessarily contains a red copy of H or a blue copy of G as a subgraph. The notion of size multipartite Ramsey number was introduced by Burger and Vuuren in 2004. This notion extends the idea of the original classical Ramsey number, multipartite Ramsey number and the size Ramsey number. In this paper, we focus on mj(H,G) and find a lower bound for mj(H,G) based on the chromatic number of H and the order of G. Also, for every graph G we obtain a tight lower bound for mj(Km,G) based on m and the maximum degree of G. Furthermore, we determine the order of magnitude of mj(Km,K1,n), for j≥m≥3 and n≥2. Then, we specify the exact values of mj(Km,K1,n) for the cases m=3, m=j and j≡0orm−2(modm−1). © 2025 Elsevier B.V.
Discrete Mathematics (0012365X)347(4)
For an arbitrary graph G, a hypergraph H is called Berge-G if there is an injection i:V(G)⟶V(H) and a bijection ψ:E(G)⟶E(H) such that for each e=uv∈E(G), we have {i(u),i(v)}⊆ψ(e). We denote by BrG, the family of r-uniform Berge-G hypergraphs. For families F1,F2,…,Ft of r-uniform hypergraphs, the Ramsey number R(F1,F2,…,Ft) is the minimum integer n such that in every hyperedge coloring of the complete r-uniform hypergraph on n vertices with t colors, there exists i, 1≤i≤t, such that there is a monochromatic copy of a hypergraph in Fi of color i. Recently, the extremal problems of Berge hypergraphs have received considerable attention. In this paper, we focus on Ramsey numbers involving 3-uniform Berge cycles and prove that for n≥4, R(B3Cn,B3Cn,B3C3)=n+1. Moreover, for m≥11 and m≥n≥5, we show that [Formula presented]. This is the first result of Ramsey number for two different families of Berge hypergraphs. © 2024 Elsevier B.V.
Graphs and Combinatorics (14355914)38(1)pp. 112-120
Gyárfás et al. determined the asymptotic value of the diagonal Ramsey number of Cnk, R(Cnk,Cnk), generating the same result for k= 3 due to Haxell et al. Recently, the exact values of the Ramsey numbers of 3-uniform loose paths and cycles are completely determined. These results are motivations to conjecture that for every n≥ m≥ 3 and k≥ 3 , R(Cnk,Cmk)=(k-1)n+⌊m-12⌋,as mentioned by Omidi et al. More recently, it has been shown that this conjecture is true for n= m≥ 2 and k≥ 7 and for k= 4 when n> m or n= m is odd. Here we investigate this conjecture for k= 5 and demonstrate that it holds for k= 5 and sufficiently large n. © 2021, The Author(s), under exclusive licence to Springer Japan KK, part of Springer Nature.
Discrete Mathematics (0012365X)343(8)
For given graphs H1,…,Ht, we say that G is Ramsey for H1,…,Ht and we write G⟶(H1,…,Ht), if no matter how one colors the edges of G with t colors, say 1,…,t, there exists a monochromatic copy of Hi in the ith color for some 1≤i≤t. The multicolor Ramsey number r(H1,…,Ht) is the smallest integer n such that the complete graph Kn is Ramsey for (H1,…,Ht). The multicolor size Ramsey number rˆ(H1,…,Ht) is defined as min{|E(G)|:G⟶(H1,…,Ht)}, while the restricted size Ramsey number rˆ∗(H1,…,Ht) is defined as rˆ∗(H1,…,Ht)=min{|E(G)|:G⟶(H1,…,Ht)and|V(G)|=r(H1,…,Ht)}.In 1978 Erdős et al. initiated the study of the size Ramsey numbers of graphs. Afterwards, size Ramsey numbers have been studied with particular focus on the case of trees, sparse graphs and bounded degree graphs. In this paper, the order of magnitude of multicolor size Ramsey number of stars and cliques is determined in terms of r(K1,q,…,K1,q) and r(Kp,…,Kp). Moreover, in some special cases, restricted size Ramsey number of stars and cliques is determined exactly. Our results have, up to a constant factor, similar order of magnitude and generalize significantly a well known result of Faudree and Sheehan. © 2020 Elsevier B.V.
