# Ramsey Numbers for Theta Graphs

Authors: M. M. M. Jaradat; M. S. A. Bataineh; S. M. E. Radaideh
Journal: International Journal of Combinatorics
 (2011)

---

## Abstract

The graph Ramsey numberR(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.


---

## Body

## 1. Introduction and Preliminaries

The graphs considered in this paper are finite, undirected, and have no loops or multiple edges. For a given graphG, we denote the vertex set of a graph G by V(G) and the edge set by E(G). The cardinalities of these sets are denoted by ν(G) and ℰ(G), respectively. Throughout this paper a cycle on m vertices will be denoted by Cm, the complete graph on n vertices by Kn.  Suppose that V1⊆V(G) and V1 is non-empty, the subgraph of G whose vertex set is V1 and whose edge set is the set of those edges of G that have both ends in V1 is called the subgraph of G induced by V1, denoted by G[V1].  Let C  be a cycle in a graph G, an edge in E(G[C])∖E(C) is called a chord of C. Further, a graph G  has a θk-graph if G  has a cycle Ck that  has a chord in G. Let G  be a graph and u∈V(G). The degree of a vertex u  in G, denoted by dG(u), is the number of edges of G  incident to u. The neighbor-set of a vertex u of G in a subgraph H of G, denoted by NH(u), consists of the vertices of H adjacent to u. The circumference,c(G), of the graph G is the length of the longest cycle of G. For vertex-disjoint subgraphs H1 and H2 of G we let E(H1,H2)={xy∈E(G):x∈V(H1),y∈V(H2)} and ℰ(H1,H2)=|E(H1,H2)|.The graph Ramsey numberR(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.It is well known that the problem of determining the Ramsey numbers for complete graphs is very difficult, and it is easier to deal with paths, trees, cycles, and theta graphs. See the updated bibliography by Radziszowski [1]. In this paper we study R(F1,F2) in the case when both F1 and F2 are theta graphs.The results concerning Ramsey numbers for cycles were established by Chartrand and Schuster [2] (for k<7), by Bondy and Erdös [3] (for n=k odd and for the case when k is much smaller than n), and for all the remaining values by Rosta [4] and by Faudree and Schelp [5], independently. These results are summarized in the following theorem.Theorem 1.1.
Let3≤m≤n be integers. Then
(1.1)R(Cn,Cm)={6ifm=n=3or4,n+m2-1ifn,mareeven,(n,m)≠(4,4),max⁡{n+m2-1,2m-1}ifnisodd,miseven,2n-1ifmisodd,(n,m)≠(3,3).In order to prove our results, we need to state the following results.Theorem 1.2 (see [6]).
LetG be a graph on n vertices with no cycles of length greater than k. Then ℰ(G)≤(1/2)k(n-1)-(1/2)r(k-r-1) where r=(n-1)-(k-1)⌊(n-1)/(k-1)⌋.Theorem 1.3 (see [7]).
Every non-bipartite graphG on n vertices with more than ⌊(n-1)2/4⌋+1 edges contains cycles of every length l, where 3≤l≤c(G).Theorem 1.4 (see [8]).
LetG be a non-bipartite graph on n≥7 vertices and G contains no θ4-subgraph. Then ℰ(G)≤⌊(n-1)2/4⌋+2.Theorem 1.5 (see [9]).
LetG be a non-bipartite graph on n≥9 vertices and G contains no θ5-subgraph. Then ℰ(G)≤⌊(n-1)2/4⌋+1.In this paper, we consider Ramsey numbers for theta graphs. We determineR(θ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 (1.2)R(θn,θn)={(3n2)-1ifniseven,2n-1ifnisodd.Throughout this paper (Figures1–5), solid lines represent red edges and dashed lines represent blue edges.Figure 1
This figure represents the red edges inK9.Figure 2
This figure depicts the case whenx8 is adjacent to two nonconsecutive vertices of C5.Figure 3
This figure represents the situation in Subcase1.1.Figure 4
This figure represents the situation in Subcase1.2.Figure 5
This figure represents the situation in Subcase1.3.


## 2. Main Result

In the following lemma we determine the Ramsey numberR(θ4,C3).Lemma 2.1.
The Ramsey numberR(θ4,C3)=7.Proof.
First we show thatR(θ4,C3)≥7. Let K6 be colored as follows: the vertex set V(K6) is the disjoint union of two subsets H1 and H2 each of order 3 and completely colored red. All edges between H1 and H2 are colored blue. This coloring contains neither a red θ4-graph nor a blue C3. So, we conclude that R(θ4,C3)≥7.
It remains to show thatR(θ4,C3)≤7. Let a red-blue coloring of K7 be given. By Theorem 1.1, K7 has a red C3 or a blue C3.  If K7 has a blue C3, then the result is obtained. So we need  to consider the case when K7 has a red C3. Let x1,x2,…,x7 be the vertices of K7 and assume x1,x2,x3 are the vertices of the red C3. Any vertex of the remaining vertices x4,x5,x6, and x7 is adjacent to the red C3 by at least 2 blue edges as otherwise a red θ4-graph is produced. Assume K7[x4,x5,x6,x7] has a blue edge, say x4x5, then K7[x1,x2,x3,x4,x5] has a blue C3. So, we need to consider that K7[x4,x5,x6,x7] has no blue edge. Thus, a red θ4-graph is produced. This completes the proof.In the following lemma we determine the Ramsey numberR(θ4,θ4).Lemma 2.2.
The Ramsey numberR(θ4,θ4)=10.Proof.
First we show thatR(θ4,θ4)≥10. Let K9 be colored as follows: The vertex set V(K9) is the disjoint union of three subsets G1,G2, and G3 each of order 3 and completely colored red and the red edges between G1, G2, and G3 are shown in Figure 1. The remaining edges are colored blue.
This coloring contains neither a red nor a blueθ4-graph. So, we conclude that R(θ4,θ4)≥10. It remains to show that R(θ4,θ4)≤10. Let a red-blue coloring of K10 be given. By Theorem 1.1, K10 contains a red or a blue C3. Without loss of generality we assume that K10 has a red C3. Let x1,x2,…,x10 be the vertices of K10 and assume x1x2x3x1 be the red C3 in K10. Observe that H1=K10[x4,x5,…,x10] has a red C3 or a blue C3. So, we consider the following two cases.
Case 1.
SupposeH1 has a red C3, say x8x9x10x8. Let x4,x5,x6, and x7 be the remaining vertices in K10. Suppose H2=K10[x4,x5,x6,x7] has no blue edge, then K10 has a red θ4-graph. So, we need to consider the case when H2 has a blue edge, say x4x5 is the blue edge. Observe that any vertex in H2 must be adjacent to each of K10[x1,x2,x3] and K10[x8,x9,x10] by two blue edges as otherwise a red θ4-graph is produced. Thus x4 and x5 incident with two blue edges that have a common vertex in K10[x1,x2,x3] and incident with two blue edges that have a common vertex in K10[x8,x9,x10] and so a blue θ4-graph is produced.
Case 2.
Now we need to consider the case whenH1 has a blue C3, say x8x9x10x8. Observe that every vertex in the red C3 is adjacent to the blue C3 by two red edges as otherwise a blue θ4-graph is produced. Further, every vertex in the blue C3 is adjacent to the red C3 by two blue edges as otherwise a red θ4-graph is produced.
Thus, there are at least six red edges between the redC3 and the blue C3 and at least six blue edges between the blue C3 and the red C3. We know that, ℰ(C3,C3)=9. This is a contradiction.Now, we begin with the following construction which will be used throughout our results. Letn≥4. Then, in K2n-2 color the edges of a complete bipartite graph Kn-1,n-1 with blue and all the remaining edges with red. Then this coloring contains neither a red θn-graph nor a blue θm-graph where m=4,5. Thus, R(θn,θm)≥2n-1 where m=4,5. In the following lemma we determine the Ramsey number R(θ5,θ5)=9.Lemma 2.3.
The Ramsey numberR(θ5,θ5)=9.Proof.
It is enough to show thatR(θ5,θ5)≤9. Let a red-blue coloring of K9 be given that contains neither a red θ5-graph nor a blue θ5-graph. By Theorem 1.1, K9 must contain a blue C5 or a red C5. Without loss of generality we assume that K9 has a red C5. Let x1,x2,…,x9 be the vertices of K9 and assume x1x2x3x4x5x1 is the red C5. Define H1=K9[x1,x2,x3,x4,x5] and  H2=K9[x6,x7,x8,x9]. Now we have the following observations.(i)
H1 has no red chord as otherwise a red θ5-graph is produced. Thus, H1 contains a blue C5.(ii)
Every vertex inH2 is adjacent by at most 3 red (blue) edges to H1 as otherwise a red (blue) θ5-graph is produced.(iii)
If a vertex inH2 is adjacent to H1 by 3 red (blue) edges, then it must be adjacent to 3 consecutive vertices in H1 with red (blue) color as otherwise K9 would have a red (blue) θ5-graph ((a,b,c) are consecutive with red (blue) if a is adjacent to b with a red (blue) edge and b is adjacent to c with a red (blue) edge).(iv)
Assume there are two vertices inH2, say x6 and x7 are adjacent to H1 by 3red (blue) edges each. Then x6 and x7 are adjacent to 3 consecutive vertices in H1 and |NH1(x6)∩NH1(x7)|=1 as otherwise a red (blue) θ5-graph is produced.(v)
There are exactly two vertices inH2 adjacent to vertices of H1 by exactly 3 red edges and two blue edges each, say x6 and x7, and so each of x8 and x9 is adjacent to vertices of H1 by exactly 3 blue edges and two red edges.
To this end, one can notice from the above observations that ifx8 is adjacent to two nonadjacent vertices of C5 by the red edges, then a red θ5-graph is produced (Figure 2 depicts the situation), a contradiction. If x8 is adjacent to two adjacent vertices of C5 by the red edges, then x8 adjacent to three non-consecutive vertices (of the internal blue cycle) by blue edges. And so a blue θ5-graph is produced, a contradiction. This completes the proof.In the following lemma we determine the Ramsey numberR(θ4,θ5).Lemma 2.4.
The Ramsey numberR(θ4,θ5)=9.Proof.
It is enough to show thatR(θ4,θ5)≤9. Let a red-blue coloring of K9 be given. By Lemma 2.3, K9 must contain a blue or a red θ5-graph. If K9 contains a blue θ5-graph, then we are done. So, suppose K9 has a red θ5-graph. So, K9 has a red triangle. Let T1=x1x2x3x1 be the red triangle. Let y1,y2,…,y6 be the remaining vertices. By Theorem 1.1, H=K9[y1,y2,…,y6] has a red or a blue C3. We consider the following two cases.
Case 1.
H contains a blue C3. Let T2=y1y2y3y1 be the blue C3. Every vertex in the blue C3 is adjacent at least by two blue edges to T1, as otherwise K9 would has a red θ4-graph. Let dT2blue(xi) denote the number of blue edges from xi to T2. We consider 3 subcases according to the number of blue edges of x1,x2, and x3 to T2.
Subcase 1.1.
dT2blue(x1)=dT2blue(x2)=dT2blue(x3)=2, then a blue θ5-graph is produced. Figure 3 depicts the situation.Subcase 1.2.
dT2blue(x1)=3=dT2blue(x2) and dT2blue(x3)=0, then a blue θ5-graph is produced. Figure 4 depicts the situation.Subcase 1.3.
dT2blue(x1)=1,dT2blue(x2)=3,anddT2blue(x3)=2, then a blue θ5-graph is produced. Figure 5 depicts the situation.
Case 2.
H contains a red C3, say T2=y1y2y3y1. Let y4,y5,y6 be the remaining vertices of K9. Observe that each vertex of y4,y5,y6 is adjacent to at least two vertices of each T1 and T2 which are colored by blue, as otherwise, G contains a red θ4-graph. Hence, if K9[y4,y5,y6] has a blue edge, say y5y6, then a blue C3 is produced. Hence, by the above case a blue θ5-graph is produced. So, we need to consider the case when K9[y4,y5,y6] has no blue edges. Observe that the number of blue edges in K9 is at least 18. Further, the induced graph by blue edges is non-bipartite. By Theorem 1.5, K9 would have a blue θ5-graph. This completes the proof.In the following lemma we determine the Ramsey numberR(θ4,θ6).Lemma 2.5.
The Ramsey numberR(θ4,θ6)=11.Proof.
It is enough to show thatR(θ4,θ6)≤11. Let a red-blue coloring of K11 be given that contains neither a red θ4 nor a blue θ6. Suppose K11 has a blue cycle of length 6. Let x1,x2,…,x11 be the vertices of K11, and assume H1=x1x2x3x4x5x6x1 is the blue C6. Then H1 has no blue chord as otherwise a blue θ6-graph is produced. So, K11[x1,x3,x5] and K11[x2,x4,x6] are red triangles. Every vertex of the remaining vertices must be adjacent to H1 by at least 4 blue edges as otherwise a red θ4-graph is produced. Now, let x7 be a vertex of the remaining vertices that is adjacent to H1 by 4 blue edges. We consider three cases.
Case 1.
x7 is adjacent to 4 consecutive vertices in H1. Assume x7 is adjacent to x1,x2,x3, and x4, then a blue θ6-graph is produced.
Case 2.
x7 is adjacent to 3 consecutive vertices and a vertex separated in H1. Assume x7 is adjacent to x2,x3,x4, and x6, then a blue θ6-graph is produced.
Case 3.
x7 is adjacent to a pair of 2 consecutive vertices separated from each other in H1. Assume x7 is adjacent to x3,x4 and x1,x6, then a blue θ6-graph is produced.
So, we need to consider thatK11 has no blue C6. We need to prove that K11 has a red θ4-graph. By contradiction, suppose K11 has no red θ4-graph. By Theorem 1.1, K11 has a red C3. So, the subgraph induced by red edges is a non-bipartite graph. By Theorem 1.4, the number of red edges is at most 27. So, the number of blue edges is at least 28. By Lemma 2.1, K11 has a blue C3. Hence, the subgraph induced by blue edges is a non-bipartite graph. By Theorem 1.3, there is a blue C6, this is a contradiction. This completes the proof.In the following theorem we determine the Ramsey numberR(θ4,θk), for k≥7.Theorem 2.6.
The Ramsey numberR(θ4,θk)=2k-1,k≥7.Proof.
It is enough to show thatR(θ4,θk)≤2k-1,  k≥7. We prove it by contradiction. Let a red-blue coloring of K2k-1 be given. Suppose K2k-1 has a blue cycle of length k. Let x1,x2,…,x2k-1 be the vertices of K2k-1, and assume H=x1x2⋯xkx1 is the blue Ck. Then H has no blue chord as otherwise a blue θk-graph is produced. So, H contains a red θ4-graph. This is a contradiction.
Now, we need to consider the case whenK2k-1 has no blue cycle of length k. By Theorem 1.1, K2k-1 contains a red  C3. Let G1 be the induced subgraph of the blue edges. Note that the subgraph induced by the red edges is a non-bipartite graph and contains no red θ4. Hence, the number of red edges is at most (2k-2)2/4+2. Thus, the number of blue edges is
(2.1)E(G1)≥(2k-1)(2k-2)2-(2k-2)24-2=k2-k-2>k2-2k+3≥(2k-2)24+2.
Observe that G1 is a non-bipartite graph (R(θ4,C3)=7 and K2k-1 does not contain a red θ4-graph and so it contains a blue C3, Lemma 2.1). If c(G1)≥k, then by Theorem 1.3, G1 has a blue Ck, this is a contradiction. If c(G1)≤k-1, then by Theorem 1.2(2.2)E(G1)≤k2-2k+1,
which contradicts the inequality (2.1) for k≥7. This completes the proof.In the following theorem we determine the Ramsey numberR(θ5,θk), for k≥6.Theorem 2.7.
The Ramsey numberR(θ5,θk)=2k-1,k≥6.Proof.
It is enough to show thatR(θ5,θk)≤2k-1, k≥7. We prove it by contradiction. Let a red-blue coloring of K2k-1 be given. Suppose K2k-1 has a blue cycle of length k. Let x1,x2,…,x2k-1 be the vertices of K2k-1, and assume H=x1x2⋯xkx1 is the blue Ck. Then H has no blue chord as otherwise a blue θk-graph is produced. So, H contains a red θ5-graph. This a contradiction.
Now, we consider the case whenK2k-1 has no blue Ck. Now, we have the following observations.
(i)
R(θ4,θk)=2k-1,  k≥7. Thus, the induced graph on the red edges is a non-bipartite graph.(ii)
R(θ5,θ4)=9. Thus, the induced graph by the blue edges is a non-bipartite graph.
LetG1 be the graph induced by the blue edges. Since K2k-1 has no red θ5-graph, by Theorem 1.5 the number of red edges is at most (2k-2)2/4+1. Thus, as in the above theorem,
(2.3)E(G1)≥(2k-2)(2k-1)2-(2k-2)24-1=k2-k-1
edges. If c(G1)≥k, then by Theorem 1.3, there is a blue Ck. This is a contradiction. If c(G1)≤k-1, then
(2.4)E(G1)≤k2-2k+1.
This contradicts the inequality (2.3) for k≥6.Theorem 2.8.
Forn≥6,
(2.5)R(θn,θn)={(3n2)-1ifniseven,2n-1ifnisodd.Proof.
First we consider the case whenn is odd. In K2n-2 color the edges of two vertex disjoint complete graphs of order n-1 with a red color and the remaining edges with a blue color. This coloring contains neither a red nor a blue θn-graph. We conclude that R(θn,θn)≥2n-1.
Let a red-blue coloring ofK2n-1 be given that contains neither a red nor a blue θn. We know, by Theorem 1.1, that R(Cn,Cn)=2n-1. Thus, K2n-1 contains either a red or a blue Cn. Without loss of generality, we suppose that K2n-1 has a blue Cn. Then there are no chords in Cn as otherwise a blue θn is produced. So, K2n-1 contains a red θn. This is a contradiction.
Now we consider the case whenn is even. Let K(3n/2)-2((3n/2)-2) be colored with two colors, say red and blue, as follows: the edges of vertex disjoint Kn-1 and Kn/2-1 are colored blue and the remaining edges are colored red. This coloring contains neither a red nor a blue θn. We conclude that R(θn,θn)≥(3n/2)-1.
To show thatR(θn,θn)≤(3n/2)-1, we follow, word by word, the above argument when n is odd by taking into account that R(Cn,Cn)=(3n/2)-1. The proof is complete.We conclude this paper by highlighting an interesting open problem. We begin with the following constructions.Letn≥m≥6. If θm contains an odd cycle, then in K2n-2 color the edges of a complete bipartite graph Kn-1,n-1 with blue and all the remaining edges with red. This coloring contains neither a red θn-graph nor a blue θm-graph. Thus, R(θn,θm)≥2n-1.Now, we consider the case whenθm contains no an odd cycle. If n is even, then in Kn+(m/2)-2, color the edges of a complete bipartite graph Kn-1,(m/2)-1 with blue and all the remaining edges with red. This coloring contains neither a red θn-graph nor a blue θm-graph. Thus, R(θn,θm)≥n+m/2-1. If n is odd, then in K2m-2, color the edges of a complete bipartite graph Km-1,m-1 with red and all the remaining edges with blue and in Kn+(m/2)-2, color the edges of a complete bipartite graph Kn-1,(m/2)-1 with blue and all the remaining edges with red. Km-1,m-1 and Kn-1,(m/2)-1, respectively, provide examples for lower bounds when n is odd, respectively, when θm contains no an odd cycle. Thus, R(θn,θm)≥max{n+m/2-1,2m-1}.From the above construction we conjecture that forn≥m≥6,(2.6)R(θn,θm)={2n-1ifθmcontains odd cycle,max⁡{n+m2-1,2m-1}ifn  is odd andθmdoes not contain an odd cycle,n+m2-1ifn is even andθmdoes not contain an odd cycle.



---

*Source: 649687-2011-06-15.xml*