Bipartite Ramsey number pairs that involve combinations of cycles and odd paths

Research output: Contribution to journalArticlepeer-review

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 languageEnglish
Article number114283
JournalDiscrete Mathematics
Volume348
Issue number2
DOIs
Publication statusPublished - Feb 2025

Keywords

  • Bipartite graph
  • Cycle
  • Path
  • Ramsey

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics

Fingerprint

Dive into the research topics of 'Bipartite Ramsey number pairs that involve combinations of cycles and odd paths'. Together they form a unique fingerprint.

Cite this