2023/04/17 by Yiran Zhang, Zhang, Yiran, Yuejian Peng +1
Mathematics · Computer Science · #Limits and Structures in Graph Theory #Advanced Graph Theory Research #Advanced Topology and Set Theory
paper · pdf · doi:10.48550/arxiv.2304.08003
For graphs G0, G1 and G2, write G0\longmapsto(G1, G2) if each red-blue-edge-coloring of G0 yields a red G1 or a blue G2. The Ramsey number r(G1, G2) is the minimum number n such that the complete graph Kn\longmapsto(G1, G2). In [Discrete Math. 312(2012)], Schelp formulated the following question: for which graphs H there is a constant 0c|V(G)|, G\longmapsto(H, H). In this paper, we prove that for any m>n, if G is a balanced bipartite graph of order 2(m+n-1) with δ(G)>(3)/(4)(m+n-1), then G\longmapsto(CMm, CMn), where CMi is a matching with i edges contained in a connected component. By Szeméredi's Regularity Lemma, using a similar idea as introduced by [J. Combin. Theory Ser. B 75(1999)], we show that for every η>0, there is an integer N0>0 such that for any N>N0 the following holds: Let α1>α2>0 such that α1+α2=1. Let G[X, Y] be a balanced bipartite graph on 2(N-1) vertices with δ(G)≥((3)/(4)+3η)(N-1). Then for each red-blue-edge-coloring of G, either there exist red even cycles of each length in \4, 6, 8, …, (2-3η2)α1N\, or there exist blue even cycles of each length in \4, 6, 8, …, (2-3η2)α2N\. Furthermore, the bound δ(G)≥((3)/(4)+3η)(N-1) is asymptotically tight. Previous studies on Schelp's question on cycles are on diagonal case, we obtain an asymptotic result of Schelp's question for all non-diagonal cases.