Abstract
For bipartite graphs G1,G2,…,Gk, the bipartite Ramsey number b(G1,G2, …,Gk) is the least positive integer b, so that any coloring of the edges of Kb,b with k colors, will result in a copy of Gi in the ith color, for some i. For bipartite graphs G1 and G2, the bipartite Ramsey number pair (a,b), denoted by bp(G1,G2)=(a,b), is an ordered pair of integers such that for any blue-red coloring of the edges of Ka′,b′, with a′≥b′, either a blue copy of G1 exists or a red copy of G2 exists if and only if a′≥a and b′≥b. In [4], Faudree and Schelp considered bipartite Ramsey number pairs involving paths. Recently, Joubert, Hattingh and Henning showed, in [7] and [8], that bp(C2s,C2s)=(2s,2s−1) and b(P2s,C2s)=2s−1, for sufficiently large positive integers s. In this paper we will focus our attention on finding exact values for bipartite Ramsey number pairs that involve cycles and odd paths. Specifically, let s and r be sufficiently large positive integers. We will prove that bp(C2s,P2r+1)=(s+r,s+r−1) if r≥s+1, bp(P2s+1,C2r)=(s+r,s+r) if r=s+1, and bp(P2s+1,C2r)=(s+r−1,s+r−1) if r≥s+2.
Original language | English |
---|---|
Article number | 114283 |
Journal | Discrete Mathematics |
Volume | 348 |
Issue number | 2 |
DOIs | |
Publication status | Published - Feb 2025 |
Keywords
- Bipartite graph
- Cycle
- Path
- Ramsey
ASJC Scopus subject areas
- Theoretical Computer Science
- Discrete Mathematics and Combinatorics