![MathJax Logo](/templates/jsp/_style2/_tandf/pb2/images/math-jax.gif)
Abstract
Given any two graphs F and H, the Ramsey number R(F, H) is defined as the smallest positive integer n such that every red-blue coloring of the edges of the complete graph Kn of order n, there will be a subgraph of Kn isomorphic to F whose edges are all colored red (a red F) or a subgraph of Kn isomorphic to H whose edges are all colored blue (a blue H). If F and H are bipartite graphs, then the k-Ramsey number is defined as the smallest positive integer n such that for any red-blue coloring of the edges of the complete k-partite graph of order n in which each partite set is of order
or
there will be a subgraph isomorphic to F whose edges are all colored red (a red F) or a subgraph isomorphic to H whose edges are all colored blue (a blue H). Andrews, Chartrand, Lumduanhom and Zhang found the k-Ramsey number
for
, and for
and
where
. We continue their work by investigating the case where the graphs F and H are both C5.
Keywords:
1 Introduction
The graphs we consider in this paper are undirected and simple. Given a graph with
, the open neighborhood of v, denoted N(v), is defined as the set of all vertices adjacent to v. The edges uv and vx are adjacent in G, while the edges vx and wy are nonadjacent. The number of vertices in a graph G is the order of G and the number of edges is the size of G. We will use n and m for the order and size, respectively, of a graph. For notations not defined here, we refer the reader to [Citation2].
In a red-blue coloring of (the edges of) a graph G, every edge of G is colored red or blue. For two graphs F and H, the Ramsey number R(F, H) of F and H is the smallest positive integer n such that for every red-blue coloring of the complete graph Kn of order n, there is either a subgraph isomorphic to F all of whose edges are colored red (a red F) or a subgraph isomorphic to H all of whose edges are colored blue (a blue H). The Ramsey number R(F, H) is known to exist for each pair F, H of graphs.
In the case where F and H are bipartite, the bipartite Ramsey number BR(F, H) is defined as the smallest positive integer r such that every red-blue coloring of the r-regular complete bipartite graph results in a red F or a blue H. The bipartite Ramsey number BR(F, H) is also known to exist for each pair F, H of bipartite graphs (see [Citation4]).
For an integer , a balanced complete k-partite graph G of order
is the complete k-partite graph in which every partite set has either
or
vertices. Suppose
where
. Then
and
. Let
be the number of partite sets in G of order
. Then the number of partite sets of order
equals
. Hence,
, and
, whence
. Thus, we have k – r partite sets of order
and r partite sets of order
, and so G is isomorphic to
. If r = 0, then G is a
-regular graph, which we denote by
. If
, then we denote G by
. For bipartite graphs F and H and an integer k with
, the k-Ramsey number
is defined in [Citation1] as the smallest positive integer n such that every red-blue coloring of a balanced complete k-partite graph of order n produces either a red F or a blue H.
For two sets X and Y of vertices of a graph G, the set of edges in G joining a vertex in X and a vertex in Y is denoted by . The subgraph induced by
is denoted by
or just
if the context is clear. The subgraph induced by X is denoted by
or just
if the context is clear.
Let and consider the complete k-partite graph
. Let
denote the partite sets of G. Then
. Let (R, B) be any two-coloring of G. Then, as we have a 2-coloring of the edges of
and
, either a blue F or a red H is produced in
and therefore in G. Thus,
and so
exists. In [Citation1], a formula for
is presented for each pair
of stars of sizes
and
, respectively, and each integer k with
where
. The authors also determine
where
.
For a red-blue coloring (R, B) of a graph G, let GR and GB denote the red and blue subgraphs of G, respectively.
It is not necessarily the case that exists when F and H are not bipartite, which was pointed out by Johnston in his Ph.D. dissertation [Citation5]. To see this, let G be any balanced complete 2-bipartite graph. No matter how we color the edges of G, there is no subgraph isomorphic to F all of whose edges are colored red nor is there a subgraph isomorphic to H all of whose edges are colored blue. Next, consider the case when k = 3. Let G be any balanced complete 3-partite graph with partite sets V1, V2 and V3. Assigning the color red to every edge of
and blue to all other edges of G results in GR and GB both being bipartite. Thus,
does not exist if both F and H are not bipartite. For k = 4, let G be a balanced complete 4-partite graph with partite sets
and V4 and color each edge of
and
red and assign blue to all other edges of G. Then both GR and GB are bipartite. Thus,
does not exist if both F and H are not bipartite.
We note next that does not exist. To see this, let G be a balanced complete 5-partite graph with partite sets Vi for
. If the edges in
,
are colored red and all other edges are colored blue, then G does not contain a monochromatic K3. Consequently,
only exists when
, since then
.
The Ramsey number for two cycles was independently obtained by Faudree and Schelp [Citation3] and Rosta [Citation7].
Theorem 1.
The following result is due to Johnston.
Theorem 2.
[Citation5] Let , and let
for
. For integers
, the Ramsey number
.
Recall that does not exist for
, and note that
by Theorem 1. Our goal in this paper is to show that
for
.
2 Preliminary remarks
We begin this section by stating results that will be used in the remainder of the paper.
Let n be a positive integer and G a graph. We define to be the largest number of edges possible in a graph on n vertices that does not contain G as a subgraph. Reiman determined the following upper bound on
.
Theorem 3.
[Citation6] Let n be a positive integer. Then .
Lemma 4.
Let H be a graph of order five. If , then H has a 5-cycle.
Proof.
The result is obviously true for m(H) = 9 or m(H) = 10.
Next consider the case when m(H) = 8. Let . If two adjacent edges, say
and
, are omitted, then
is one 5-cycle of H. If two nonadjacent edges, say
and
are omitted, then
is a 5-cycle of H. □
Lemma 5.
Let H be a graph of order five obtained from K5 by deleting exactly one edge. Delete two nonadjacent edges from H to form the graph . Then
has a 5-cycle.
Proof.
Let and suppose
is the deleted edge. Consider any two nonadjacent edges e and f of G. Suppose first that e and f are both incident with v1 and v2, say
and
. Then
is a 5-cycle of
. Next suppose that exactly one of e or f is incident with a vertex in
, say
. But then
, and
is a 5-cycle of
. □
Next we show that determining for
reduces to showing that
. Consider the following complete multipartite graphs Gk for
:
Note that for
.
Observation 6. If , then
for
.
Proof.
Let and consider any 2-coloring
of the edges of
. Then, as
, the coloring C induces a 2-coloring on the edges of Gk. Moreover, as
, either the red subgraph of this induced coloring contains a C5 or the blue subgraph of this induced coloring contains a C5. As
, it now follows that the red subgraph associated with C contains a C5 or the blue subgraph associated with C contains a C5, whence
. □
Consider the following complete multipartite graphs Hk for :
As , there exists a 2-coloring C of the edges of K8 such that neither the red graph nor the blue graph has a 5-cycle. Note that
, and that the coloring C induces a coloring on the edges of Hk containing no monochromatic 5-cycle for
, whence
for
. Thus, if we can show that
, then, by Observation 6 and the latter remark, it follows that
for
.
3 Main result
We now show that .
Theorem 7.
.
Proof.
Let and assume to the contrary that there exists a red-blue coloring of the edges of G that contains neither a red C5 nor a blue C5. Note that
. Further, let GR and GB denote the subgraphs of G induced by the red edges and the blue edges of G respectively. Lastly, let mR and mB denote the size of GR and GB respectively. Then
Without loss of generality, suppose . The graph GR is not a forest as
. By Theorem 3, we have
which implies that GR has a 4-cycle, as
. Let
denote the length of a longest cycle of GR. Then, as GR does not contain a 5-cycle, we have
. We now consider each of these possibilities for
. Let
be a longest cycle in GR and let
. Let G1 (G2, respectively) be the subgraph induced by V(C) (
, respectively) in GR, and let G3 be the subgraph of GR induced by the edges
. Lastly, let mi denote the size of the graph Gi for i = 1, 2, 3. Note that
. □
Case 1.
.
As , we see that
.
We first establish a few useful facts.
Fact 1. If , then G2 does not contain a 4-cycle
such that
.
Proof.
Suppose G2 contains a 4-cycle
such that
. As
, we have two consecutive vertices on
which are adjacent to
. Without loss of generality, assume
. Then
is a 5-cycle in GR, which is a contradiction. The result now follows.
Fact 2. Suppose . Then
. Moreover, if
, then u is adjacent to two nonconsecutive vertices of C, and
.
Proof.
By Fact 1, we have . If
, say, then v2 is not adjacent to v4, since otherwise
is a 5-cycle of GR, which is a contradiction. Thus, if
, then
. □
Fact 3. Let G21 be a nontrivial component of G2 and let . If
, then
for all
.
Proof.
Let and suppose
. Without loss of generality, assume
. Let
. As G21 is connected, there is a nontrivial path P joining u and v. If v is adjacent to v2, then P followed by the vertices
is a t-cycle of GR where
, which is a contradiction. Thus, v is not adjacent to v2, and, by symmetry, neither is v adjacent to v4. If v is adjacent to v3, then P followed by the vertices
is a t-cycle of GR, where
, which is a contradiction. If v is adjacent to v1, then P followed by the vertices
is a t-cycle of GR, where
, which is a contradiction. Thus,
. □
Fact 4. Let G21 be a nontrivial component of G2. Then . Moreover, if
for some
, then
.
Proof.
If for some
, then, by Fact 3, we have
for all
, and so
. Thus,
for all
, and so
. □
Fact 5. Let G21 be a non-trivial component of G2. If for some
, then
.
Proof.
Let G21 be a nontrivial component of G2 and suppose for some
. Without loss of generality, assume
. Note that
.
We show that : Let
. If v = v1, then
. Thus,
. Let
be adjacent to v. If
, then
, which is a contradiction. Hence,
. As G21 is connected, there exists a path P joining u and
. If
, say v = v2, then P followed by
is a t-cycle of GR for
, which is a contradiction. If v = v3, then P followed by
is a t-cycle of GR for
, which is a contradiction.
Thus, . □
Fact 6. Let be the nontrivial components of G2 for
, let
for
and let
. Then
.
Proof.
For simplicity, let . Without loss of generality, assume ui for
are isolated in G2. Then, by Facts 2 and 4,
. Thus,
. If
for some
, then, by Fact 2, we have
, and so
. Otherwise,
for
, and so
, whence
. It now follows that
. □
Note that , since otherwise GR has a 5-cycle (cf. Lemma 4).
Subcase (i):
.
As and
, we have
, and so
. First consider the case when
. As
, we have that
, and so
. Then c = 2 and so
, whence
, which is a contradiction. Next consider the case when
. In this case,
. If c = 2, then
, whence
, which is a contradiction. If c = 3, then
or
, whence
, which is a contradiction.
Subcase (ii):
.
Note that G2 has at most two nontrivial components, since otherwise . If G2 has two nontrivial components, then
or
, whence
, which is a contradiction. Thus, G2 has one nontrivial component. Let D denote the graph obtained from K4 by deleting an edge. Then
(having size 1),
(having size 2),
(having size 3),
where H is a connected subgraph of order four or G2 is connected. As
, we must have that
or G2 is connected.
First consider the case when . Let v5 be the isolated vertex of G2 and let
. If
, then, by Fact 2, we have
, and so
. If
, then, as
, we have
. As
, we see that
. If
for some
, then, by Fact 4, we have
, which is a contradiction. Thus, every vertex of D is adjacent to at most one vertex of C. As
and D has order four, we see that every vertex of D is adjacent to exactly one vertex of C. By Fact 5, every vertex of D is adjacent to the same vertex of C, say v1. But then D contains a 4-cycle
such that
, which contradicts Fact 1.
Next, consider the case when G2 is connected. If for some
, then
(cf. Fact 4), and it follows that
, which is a contradiction. Thus,
for
. If
for some
, then
, which is a contradiction. Thus, every vertex of G2 is adjacent to exactly one vertex of C. By Fact 5, every vertex of G2 is adjacent to the same vertex of C, say v1.
Before proceeding further, we prove the following useful result.
Lemma 8.
G2 contains P4 as a subgraph.
Proof.
If , then
, and so
, which is a contradiction.
For simplicity, assume . Assume, without loss of generality, that u1 is the vertex of maximum degree in G2 and that
.
First consider the case when . Then
, since otherwise
, which is a contradiction. Note that u2 and u3 are nonadjacent in G2, since otherwise
is a component of G2, which is a contradiction. Thus, u2 is adjacent to u4 (say), and
is a path of order four in G2.
Next consider the case when . As G2 is connected, u5 must be adjacent to ui in G2 for some
, say u2. But then
is path of order four in G2
Lastly, consider the case when . Then, as
, two vertices of
must be adjacent in G2, say u2 and u3. But then
is a path of order four in G2. □
Let P be a path of order 4 of G2. As v1 is adjacent to every vertex of G2, v1 is adjacent to the endpoints of P which forms a 5-cycle in GR, which is a contradiction.
Subcase (iii):
.
Reasoning as previously, we see that or G2 is connected.
First consider the case when . Let v5 be the isolated vertex of G2 and let
. If
, then, by Fact 2, we have
, and so
. If
, then, as
, we have
. As
, we see that
. If
for some
, then, by Fact 4, we have
, which is a contradiction. Thus, every vertex of K4 is adjacent to at most one vertex of C. As
and
, we see that at least three vertices of K4 are adjacent to exactly one vertex of C. By Fact 5, at least three vertices of K4 are adjacent to the same vertex of C, say v1. As
, the graph G2 contains a 4-cycle
such that
, which contradicts Fact 1.
Next, consider the case when G2 is connected. If for some
, then
, and so
, which is a contradiction. Thus,
for
. As
and
, we see that
. Thus, we see that at least four vertices of G2 are adjacent to exactly one vertex of C. By Fact 5, at least four vertices of G2 are adjacent to the same vertex of C, say v1.
Lemma 9.
G2 contains a P4 with both its endpoints adjacent to v1.
Proof.
For simplicity, let . If
, then
, which is a contradiction. Thus,
.
First consider the case when . Suppose u1 is a vertex of maximum degree in G2, and suppose, without loss of generality, that
. If
, then we have a 4-cycle
in G2 such that
, which contradicts Fact 1. Thus, v5 is adjacent to exactly one vertex of
and nonadjacent to u1. As
, the graph
. As
, the graph G2 contains a 4-cycle
such that
, which contradicts Fact 1.
Next consider the case when . Suppose u1 is a vertex of maximum degree in G2, and suppose, without loss of generality, that
. As
, the graph
contains exactly two edges.
First consider the case when these two edges are adjacent, i.e. suppose ui is adjacent to uj and uk where i, j and k are distinct integers in the set . Then
is a 4-cycle in G2 such that
, which contradicts Fact 1.
Next consider the case when these two edges are nonadjacent, i.e. suppose and
are edges with
. If ui is not adjacent to v1, then
is a P4 with both endpoints adjacent to v1. If uj is not adjacent to v1, then
is a P4 with both endpoints adjacent to v1. If uk is not adjacent to v1, then
is a P4 with both endpoints adjacent to v1. If
is not adjacent to v1, then
is a P4 with both endpoints adjacent to v1. Lastly, if u1 is not adjacent to v1, then
is a P4 with both endpoints adjacent to v1. □
As G2 contains a P4 with both its endpoints adjacent to v1, we see that v1 followed by the path of order four followed by v1 is a 5-cycle of GR, which is a contradiction.
Subcase (iv):
Reasoning as before, we see that G2 is connected. If for some
, then
, and so
, which is a contradiction. Thus,
for
. As
and
, we see that
. Thus, we see that at least three vertices of G2 are adjacent to exactly one vertex of C. By Fact 5, at least three vertices of G2 are adjacent to the same vertex of C, say v1.
If G2 is C4-free, then, by Theorem 3,
As , we may assume G2 has a 4-cycle. For simplicity, assume
where
(say) forms a 4-cycle
.
As G2 is connected, vertex u5 is adjacent to some vertex of , say u3. To avoid a 5-cycle, u5 is not adjacent to u2 or u4. So, possibly u5 is adjacent to u1.
First consider the case when u5 is adjacent to only u3. Then, as , we see that
. Moreover, as
, vertex v1 is adjacent to at least two vertices of the clique of order 4, resulting in a 5-cycle of GR, which is a contradiction.
Next consider the case when u5 is adjacent to both u1 and u3. To avoid the 5-cycle , we see that u2 is not adjacent to u4. As
, it then follows that u1 is adjacent to u3.
If u5 is not adjacent to v1, then , which contradicts Fact 1. Thus, v1 is adjacent to u5. If v1 is not adjacent to u2, then the 4-cycle
has
, which contradicts Fact 1. Thus, v1 is adjacent to u2. But then
is a 5-cycle of GR, which is a contradiction.
Case 2.
.
As GR does not contain any 5-cycles, the pairs of vertices are not in GR, and so
.
If for all i = 7, 8, 9, then
, which is a contradiction. Assume, without loss of generality, that
and that v7 is adjacent to v1. Note that v7 cannot be adjacent to either v2 or v6, since otherwise we obtain a cycle of length 7. In order to avoid the 5-cycle
, we see that v7 is not adjacent to v4. Thus,
, and so
.
If for j = 8, 9, then
, which is a contradiction. Thus
for some
.
Subcase (i):
for some
. As before,
. But then
is a 5-clique with an edge removed in
. At most two nonadjacent edges of H are not in GB. Thus, by Lemma 5, the subgraph induced by
in GB contains a 5-cycle, which is a contradiction.
Subcase (ii):
for i = 8, 9. In this case,
is a 5-clique with an edge removed in
. Again, at most two nonadjacent edges of H are not in GB. Thus, by Lemma 5, the subgraph induced by
in GB contains a 5-cycle, which is a contradiction.
Before proceeding further, we establish the following useful Lemma.
Lemma 10.
Suppose is a 7-cycle of GR, then
.
Proof.
To avoid a 5-cycle in GR, none of the vertex pairs occur as edges of GR.
Suppose v1 and v3 are adjacent in GR. To avoid the 5-cycle , we see that v1 is not adjacent to v6. To avoid the 5-cycle
, we see that v4 is not adjacent to v6. To avoid the 5-cycle
, we see that v5 is not adjacent to v7. To avoid the 5-cycle
, we see that v3 is not adjacent to v5. If v2 is adjacent to both v4 and v7, then
is a 5-cycle, which is a contradiction. Hence, at most one of the pairs
or
is an edge of GR. Thus, if v1 and v3 are adjacent, then at most one of
or
is an edge of GR, whence
.
We may therefore assume that v1 is not adjacent to v3. Similarly, we may assume that none of the pairs are edges of GR. In this case,
. □
Case 3.
.
By Lemma 10, we have . As
and
, we see that
. Thus, either v8 or v9 is adjacent to at least three vertices of C. Without loss of generality, assume v8 is adjacent to at least three vertices of C. Moreover, suppose without loss of generality, that v8 is adjacent to v1. To avoid an 8-cycle, we see that v8 is not adjacent to both v2 and v7. To avoid the 5-cycle
, we see that v5 is not adjacent to v8. To avoid the 5-cycle
, we see that v4 is not adjacent to v8. Thus, v8 must be adjacent to both v3 and v6, and we obtain the 5-cycle
, which is a contradiction. Thus, this case cannot occur.
Lemma 11.
Suppose is an 8-cycle of GR and consider three consecutive vertices u, v, w of T. If u and w adjacent, then
.
Proof.
Assume u = v1 and w = v3 are adjacent. To avoid the 5-cycle , we see that at most one of the pairs
or
occurs as an edge in GR. To avoid the 5-cycle
, we see that v2 is not adjacent to v7. To avoid the 5-cycle
, we see that v2 is not adjacent to v6. To avoid the 5-cycle
, we see that v2 is not adjacent to v5. By Lemma 10, we have that
, whence
. □
Case 4.
.
As GR does not contain any 5-cycles, the pairs and
are not edges of GR.
Lemma 12.
Suppose u, v, w are three consecutive vertices of C. Then u is not adjacent to w.
Proof.
Suppose u, v, w are three consecutive vertices of C with u adjacent to w. Without loss of generality, assume u = v1 and that w = v3. By Lemma 11, we have , and so v9 is adjacent to at least four vertices of C.
Suppose v9 is adjacent to vertex v1. To avoid a 9-cycle, v9 is not adjacent to both v2 and v8. Note that vertex vi (i = 4, 5, 6) is the endpoint of a path P4 having v1 as its other endpoint. Thus, to avoid a 5-cycle, vertex v9 is not adjacent to any of the vertices v4, v5 or v6. But then vertex v9 is only possibly adjacent to the additional vertices v3 and v7, which implies that v9 is adjacent to at most three vertices of C, which is a contradiction. Thus, v9 is not adjacent to v1. By symmetry, v9 is not adjacent to v3.
Suppose v9 is adjacent v7. To avoid 9-cycles, v9 is not adjacent to both v6 and v8. But then v9 is adjacent to v2, v4 and v5, resulting in a 9-cycle, which is a contradiction. Thus, v9 is not adjacent to v7.
If v9 is adjacent to v5, then, to avoid a 9-cycle, vertices v4 and v6 are not adjacent to v9. The only additional vertices which v9 can be adjacent to are v2 and v8, which implies that v9 is adjacent to at most three vertices of C, which is a contradiction. Thus, v9 is not adjacent to v5.
It now follows that v9 is adjacent to the vertices v2, v4, v6 and v8, which form the 5-cycle , which is a contradiction.
Thus, v1 is not adjacent to v3. The result now follows. □
Suppose v9 is adjacent to a vertex of C, say v1. To avoid a 9-cycle, v9 is not adjacent to both v2 and v8. Note that vertex vi (i = 4, 6) is the endpoint of a path P4 having v1 as its other endpoint. Thus, to avoid a 5-cycle, vertex v9 is not adjacent to both v4 and v6. By Lemma 12, we see that induces a 5-clique in
. Thus, by Lemma 4, the subgraph induced by
in GB contains a 5-cycle, which is a contradiction.
Thus, v9 is not adjacent to any vertices of C and again the subgraph induced by
in GB contains a 5-cycle, which is a contradiction.
Case 5.
.
First consider the case when we have three consecutive vertices u, v, w on the cycle C with u adjacent to w. Without loss of generality, assume u = v1 and w = v3. Let . To avoid the 5-cycle
, we see that v2 is not adjacent to v8. By symmetry, we see that v2 is not adjacent to vertex v5 either. To avoid the 5-cycle
, we see that v2 is not adjacent to v7. By symmetry, v2 is not adjacent to v6 either. To avoid the 5-cycle
, we see that at most one of the pairs
and
is an edge of GR. Thus,
.
Suppose are three consecutive vertices of
such that
and
are adjacent. Then, by Lemma 11,
, and so
, which is a contradiction.
Thus, if are three consecutive vertices of
, then
is not adjacent to
. So, the pairs
,
,
are not edges of GR. Recall that v2 is not adjacent to any of the vertices in the set
. To avoid the 5-cycle
, the pair
is not an edge. To avoid the 5-cycle
, the pair
is not an edge. To avoid the 5-cycle
, vertex v3 is not adjacent to v7. To avoid the 5-cycle
, vertex v3 is not adjacent to v8. To avoid the 5-cycle,
, vertex v4 is not adjacent to v8. To avoid the 5-cycle
, vertex v4 is not adjacent to v9. To avoid the 5-cycle
, vertex v5 is not adjacent to v9. To avoid the 5-cycle
, only one of the pairs
and
may be an edge of GR. To avoid the 5-cycle
, only one of the pairs
and
may be an edge of GR. Recall that at most one of the pairs
and
may be edge of GR. The pair
may be an edge of GR, and so
, which is a contradiction.
We therefore assume that if we have three consecutive vertices u, v, w on the cycle C, then u is not adjacent to w. Thus, is a cycle in
.
To avoid the 5-cycle , vertex v1 is not adjacent to v5. To avoid the 5-cycle
, vertex v1 is not adjacent to v6.
Similarly, pairs are not edges of GR. Only an additional 9 edges may be in GR.
We next show that v5 and v8 are not adjacent. Suppose, to the contrary, that v5 and v8 are adjacent. To avoid the 5-cycle , we see that v2 is not adjacent to v8. To avoid the 5-cycle
, we see that vertex v3 is not adjacent to v9. To avoid the 5-cycle
, we see that vertex v2 is not adjacent to v5. Thus, we have ten edges in GR so far, with only five additional edges which may be in GR. Thus,
, which is a contradiction.
We conclude that v5 and v8 are not adjacent, and, by symmetry, that v3 and v6 are not adjacent. It now follows that induces a
in
. By Lemma 5, the subgraph induced by
in GB has a 5-cycle, which is a contradiction.
References
- Andrews, E., Chartrand, G., Lumduanhom, C., Zhang, P. (2017). Stars and their k-Ramsey numbers. Graphs Comb. 33: 257–274.
- Chartrand, G., Lesniak, L., Zhang, P. (2016). Graphs & Digraphs, 6th ed. Boca Raton, FL: CRC Press/Taylor & Francis Group.
- Faudree, R. J., Schelp, R. H. (1974). All Ramsey numbers for cycles in graphs. Discrete Math. 8: 313–329.
- Hattingh, J. H., Henning, M. A. (1998). Bipartite Ramsey theory. Util. Math. 53: 217–230.
- Johnston, D. (2015). Edge colorings of graphs and their applications. Dissertations. 586. http://scholarworks.wmich.edu/dissertations/586.
- Reiman, I. (1958). Über ein problem von K. Zarankiewicz. Acta. Math. Acad. Sci. Hungar. 9: 269–273.
- Rosta, V. (1973). On a Ramsey type problem of J.A. Bondy and P. Erdös I & II. J. Comb. Theory Ser. B. 15: 94–120.