Ramsey Numbers for Theta Graphs

Abstract EN

The graph Ramsey number R(F1,F2) is the smallest integer N with the property that any complete graph of at least N vertices whose edges are colored with two colors (say, red and blue) contains either a subgraph isomorphic to F1 all of whose edges are red or a subgraph isomorphic to F2 all of whose edges are blue.

In this paper, we consider the Ramsey numbers for theta graphs.

We determine R(θ4,θk), R(θ5,θk) for k≥4.

More specifically, we establish that R(θ4,θk)=R(θ5,θk)=2k-1 for k≥7.

Furthermore, we determine R(θn,θn) for n≥5.

In fact, we establish that R(θn,θn)=(3n/2)-1 if n is even, 2n-1 if n is odd.