The-proper-Ramsey-numbers-of-$K_3$-against-$C_3$-and-$C_5$

Andrews, Eric

doi:10.61091/jcmcc117-16

Abstract

1. Introduction
2. Essential Preliminaries
3. Results
4. Concluding Remarks
Conflict of Interest

References

Journal of Combinatorial Mathematics and Combinatorial Computing

Volume 117
Pages: 177-184

Research article

The-proper-Ramsey-numbers-of- $K_{3}$ -against- $C_{3}$ -and- $C_{5}$

^¹, ^¹

¹Department of Mathematics and Statistics University of Alaska, Anchorage Anchorage, AK 99508, USA

Received: 28/11/2023
Accepted: 02/12/2023
Published: 06/12/2023

Copyright Link
License

Abstract

For graphs $F$ and $H$ , the proper Ramsey Number $P R (F, H)$ is the smallest integer $n$ so that any $χ^{'} (H)$ -edge-coloring on $K_{n}$ contains either a monochrome $F$ or a properly colored $H$ . We determine the proper Ramsey number of $K_{3}$ against $C_{3}$ and $C_{5}$ .

Keywords: Graph theory, Edge coloring, Ramsey theory, Proper Ramsey number

1. Introduction

In this paper, we give values for the proper Ramsey number of $K_{3}$ against $C_{3}$ and $C_{5}$ . Let $F$ and $H$ be graphs and $χ^{'} (H)$ the chromatic index of $H$ . The proper Ramsey number, $P R (F, H)$ , of $F$ and $H$ is defined to be the smallest positive integer $n$ so that every $χ^{'} (H)$ -edge coloring of $K_{n}$ contains either a monochrome $F$ or a properly colored $H$ . Necessarily, if $P R (F, H) = n$ , then there exists at least one coloring of $K_{n - 1}$ which contains neither. Such a coloring is called a critical coloring with respect to $P R (F, H)$ .

English et al. [1] determined $P R (F, H)$ for a variety of graph pairs in which $χ^{'} (H) = 2$ , including for $K_{3}$ against $C_{4}$ . Extending that work, Olejniczak [2] found the remaining values of $P R (K_{3}, C_{n})$ where $n$ is even. The problem we address here concerns a pair of graphs for which $χ^{'} (H) = 3$ , namely to determine $P R (K_{3}, C_{3})$ and $P R (K_{3}, C_{5})$ .

Note that the proper Ramsey number is one of several variations on the ordinary Ramsey number. It is closely related to the edge-chromatic Ramsey number introduced by Eroh [3]. The edge-chromatic Ramsey number $C R (F, H)$ is defined to be the the smallest positive integer $n$ so that if the edges of $K_{n}$ are colored with any number of colors, then the colored graph contains either a monochrome $F$ or a properly colored $H$ . Eroh [3] shows that this number exists only for certain classes of graph pairs. The proper Ramsey number, on the other hand, is a restriction of edge-chromatic Ramsey number, in the sense that we color $K_{n}$ with a fixed number of colors. Olejniczak [2] shows that the proper Ramsey number exists for all pairs of graphs $F$ and $H$ . Further variations on the Ramsey number are discussed in Chartrand and Zhang [4].

In the following, graphs are assumed to be finite, simple, and undirected. We refer to Chartrand and Zhang [5] for our graph-theoretic notation.

2. Essential Preliminaries

At several points in this paper, we shall need to select a vertex of a graph so that it is incident to the greatest number of edges of the same color. We therefore adopt the following definition.

Definition 1. Let $G$ be a graph, and let ${c_{i}}$ be the indexed family of colors of edges in $G$ . If $v$ is a vertex of $G$ , then the color degree of $v$ with respect to the color $c_{i}$ is the number of edges incident to $v$ that have the color $c_{i}$ . We denote the color degree by $d_{c_{i}} (v)$ .

Note that there must be some $i$ and some $x$ for which $d_{c_{i}} (x) \geq d_{c_{j}} (v)$ for all $j$ and for every vertex $v$ in $G$ . That is, there is some vertex incident to the greatest number of like-colored edges. The proof is trivial. Let $S = {d_{c_{i}} (v) : v \in V (G)}$ be the set of all color degrees of all vertices in $G$ . Then $S$ is a set of integers bounded above by $Δ (G)$ . It therefore has a greatest element. We denote this greatest element $Δ_{c} (G)$ and call it the maximal color degree.

We shall also require the following facts about $K_{4}$ and $K_{5}$

Lemma 1. Every $2$ -edge-coloring of $K_{4}$ that does not contain a monochrome $K_{3}$ contains a properly colored $P_{4}$ beginning with each color.

Proof. Let $G$ be a $2$ -edge-colored copy of $K_{4}$ containing no monochrome $K_{3}$ . Consider an arbitrary vertex $x$ of $K_{4}$ . Without loss of generality, suppose that $x$ is incident to more red edges than blue edges. Then $x$ is incident to either three or two red edges.

Suppose that $x$ has three red edges. Then $G$ must contain either a red or a blue $K_{3}$ . Let $x a$ , $x b$ , and $x c$ be the three red edges. Then $a b$ and $b c$ must be blue. But then $a c$ produces a monochrome $K_{3}$ regardless of whether it is red or blue. So $x$ must not have three red edges.

Suppose that $x$ has two red edges. Let $x a$ and $x b$ be red and $x c$ blue. Then $a b$ must be blue to avoid a red $K_{3}$ . So $(c, x, b, a)$ is a properly colored $P_{4}$ beginning with a blue edge. On the other hand, $b c$ and $a c$ cannot both be blue, since a blue $K_{3}$ would result. So one is red. Thus one of $(x, a, b, c)$ or $(b, x, c, a)$ is a properly colored $P_{4}$ beginning with a red edge.

Lemma 2. Any $2$ -edge-coloring of $K_{5}$ not containing a monochrome $K_{3}$ decomposes $K_{5}$ into two Hamiltonian cycles of different colors.

Proof. Let $G$ be a $2$ -edge-colored copy of $K_{5}$ . We first show that $d_{c} (v) = 2$ for every color and vertex $v$ in $G$ . Suppose otherwise. Then $d_{c_{i}} (v_{j}) \geq 3$ for some $i$ and $j$ . Without loss of generality, suppose that this vertex is labeled $a$ and the color is red. Then there are at least three vertices, label them $b$ , $c$ , and $d$ , adjacent to $a$ through a red edge. If any of the edges $b c$ , $c d$ , or $b d$ is red, a monochrome $K_{3}$ results. So none of them are red. But then they must all be blue, and again a monochrome $K_{3}$ results. Thus each monochrome subgraph of $G$ is $2$ -regular.

Consider then, the red subgraph of $G$ . This subgraph must be $C_{5}$ , since there is no other $2$ -regular graph on $5$ vertices. The same argument applies to the blue subgraph. Since these subgraphs have disjoint edge sets and identical vertex sets, they decompose $G$ into two Hamiltonian cycles of different colors.

3. Results

Theorem 1. $P R (K_{3}, C_{3}) = 11$ .

Proof. We first show that $P R (K_{3}, C_{3}) \geq 11$ . Consider the following coloring of $K_{10}$ . Consider $K_{10}$ as $K_{5} + K_{5}$ . Decompose each $K_{5}$ subgraph into two Hamiltonian cycles; in each $K_{5}$ subgraph, color one cycle red and the other blue. Color the remaining edges (those between the $K_{5}$ sugraphs) green. This coloring contains no monochrome $K_{3}$ . The red and blue subgraphs are each copies of $C_{5}$ , which do not contain $K_{3}$ . The green sugraph is $K_{5, 5}$ , which contains no odd cycles by virtue of being bipartite. Thus, the green subgraph contains no $K_{3}$

Furthermore, this coloring contains no proper $C_{3}$ . Consider any 3-cycle in this graph. Either all of the vertices lie in one $K_{5}$ subgraph, or two lie in one $K_{5}$ and the third lies in the other. In the first case, all of the edges of the cycle are either red or blue, so it cannot be properly colored. In the other, two adjacent edges are green, so it cannot be properly colored. This coloring is illustrated in Figure 1.

Figure 1. This coloring on $K_{10}$ shows that $P R (K_{3}, C_{3}) \geq 11$ .

We now show that $P R (K_{3}, C_{3}) \leq 11$ . The proof is by contradiction. Let $G$ be a $3$ -edge-colored copy of $K_{11}$ containing no monochrome $K_{3}$ and no proper $C_{3}$ . We show that this assumption leads to a contradiction. Let $v$ be a vertex of maximal color degree, and $X_{1}$ , $X_{2}$ , and $X_{3}$ the subgraphs of $G - v$ so that each $X_{i}$ is joined to $v$ entirely edges of a single color, say $X_{1}$ by red edges, $X_{2}$ by blue, and $X_{3}$ by green. Since $G$ contains no monochrome $K_{3}$ , the edges within $X_{i}$ must each be of a color different than that of the edges joining $X_{i}$ to $v$ . Since $G$ contains no proper $C_{3}$ , the edges between $X_{i}$ and $X_{j}$ must each be one of two colors, specifically those of the edges joining $X_{i}$ and $X_{j}$ to $v$ . For instance, the edges between $X_{1}$ and $X_{2}$ must all be either red or blue, since coloring any such edge green yields a proper $C_{3}$ .

We will suppose that $| X_{1} | \geq | X_{2} | \geq | X_{3} |$ , which can always be accomplished by a relabeling of colors. Note that $| X_{1} | + | X_{2} | + | X_{3} | = | G - v | = 10$ . It follows that the possible orders of these subgraphs correspond to the three-part integer partitions of 10. We consider these possibilities in order of decreasing $| X_{1} |$ .

Case 1. Suppose that $| X_{1} | \geq 6$ . Then $X_{1}$ contains a 2-edge-colored $K_{6}$ . It follows that $G$ must contain a monochrome $K_{3}$ , since $R (K_{3}, K_{3}) = 6$ . But we assumed otherwise, so this is a contradiction.

Case 2. Suppose that $| X_{1} | = 5$ . Then either $| X_{2} | \geq 3$ or $| X_{3} | \geq 3$ . Without loss of generality, suppose that $| X_{2} | \geq 3$ . Since $X_{1}$ is a $2$ -edge-colored copy of $K_{5}$ containing no monochrome $K_{3}$ , it can only be colored in one way. By Lemma 2, $X_{1}$ has one blue Hamiltonian cycle and one green Hamiltonian cycle. Similarly, $X_{2}$ must contain a proper $P_{3}$ , and so it has at least one red edge adjacent to a green edge. From the discussion above, all the edges between $X_{1}$ and $X_{2}$ are either red or blue.

Let $V (X_{1}) = {a, b, c, d, e}$ so that $(a, b, c, d, e, a)$ is the blue Hamiltonian cycle and $(a, c, e, b, d, a)$ is the green Hamiltonian cycle, and let $p$ , $q$ , and $r$ belong to $V (X_{2})$ so that $p q$ is red and $q r$ green. Consider the set of edges from $X_{1}$ to $p$ . If any three of them are blue, then a blue $K_{3}$ results, for in any set of three vertices in $V (X_{2})$ , two of them are adjacent through a blue edge. Thus, at least three of the edges from $X_{1}$ to $p$ are red. For the same reason, at least three of the edges from $X_{1}$ to $q$ are red. But this means that there exists at least one vertex of $X_{1}$ with red edges to both $p$ and $q$ , yielding a red $K_{3}$ , so this is impossible.

Case 3. Suppose that $| X_{1} | = 4$ . There are two possibilities.

Subcase 3.1.. Suppose $| X_{2} | = | X_{3} | = 3$ . By Lemma 1, $X_{1}$ contains both a blue-green-blue and a green-blue-green $P_{4}$ . We will first examine the subgraph $X_{1} + X_{2}$ . Let $V (X_{1}) = {a, b, c, d}$ so that $a b$ and $c d$ are green and $b c$ is blue. Let $V (X_{2}) = {p, q, r}$ so that $p q$ is red and $q r$ is green. Recall that all the edges between $X_{1}$ and $X_{2}$ are either red or blue. Consider the set of edges ${b q, c q}$ . At least one of these edges is red, otherwise $G [{b, c, q}]$ is a blue $K_{3}$ . (Recall that $G [X]$ is the subgraph of $G$ induced by the set of vertices $X$ .) Without loss of generality, suppose that $c q$ is red. Then we must have the following:

$c r$ must be red, otherwise $(c, q, r, c)$ is a proper $C_{3}$ .
$d q$ must be red, otherwise $(d, q, c, d)$ is a proper $C_{3}$ .
$d r$ must be red, otherwise $(c, d, r, c)$ is a proper $C_{3}$ .
$c p$ must be blue, otherwise $G [{c, p, q}]$ is a red $K_{3}$ .
$d p$ must be blue, otherwise $(c, d, p, c)$ is a proper $C_{3}$ .
$b p$ must be red, otherwise $G [{b, c, p}]$ is a blue $K_{3}$ .
$a p$ must be red, otherwise $(a, b, p, a)$ is a proper $C_{3}$ .
$b q$ must be blue, otherwise $G [{b, p, q}]$ is a a red $K_{3}$ .
$a q$ must be blue, otherwise $(a, b, q, a)$ is a proper $C_{3}$ .
$b r$ must be blue, otherwise $(b, q, r, b)$ is a proper $C_{3}$ .
$a r$ must be blue, otherwise $(a, b, r, a)$ is a proper $C_{3}$ .

It then follows that the remaining edges of $X_{1}$ must all be blue to avoid proper $3$ -cycles in $(a, d, p, a)$ , $(a, c, q, a)$ , and $(b, d, p, b)$ . The resulting graph is shown in Figure 1. Thus, $X_{1}$ has four blue edges and two green edges.

Figure 2. Coloring of $X_{1} + X_{2}$ when $| X_{1} | = 4$ , $| X_{2} | = | X_{3} | = 3$ and edge $c q$ is red. Solid edges are red, dashed edges blue, and bold edges green. Note the number of edges of each color in $X_{1}$ .

Next consider the subgraph $X_{1} + X_{3}$ . Relabel the vertices of $X_{1}$ so that $V (X_{1}) = {a, b, c, d}$ , $a b$ and $c d$ are blue, and $b c$ is green. (We are guaranteed the existence of such a path by Lemma 1.) Let $V (X_{3}) = {x, y, z}$ so that $x y$ is red and $y z$ is blue. Note that the starting conditions here are isomorphic to those in the case of $X_{1} + X_{2}$ through the permutation of the colors blue and green. It follows that $X_{1} + X_{3}$ must be colored in the same way as $X_{1} + X_{2}$ with the colors blue and green swapped. Hence, $X_{1}$ must have four green edges and two blue edges.

But then $X_{1}$ must have both four green edges and four blue edges, a contradiction since $X_{1}$ has only six edges.

Subcase 3.2.. Suppose that $| X_{2} | = 4$ and $| X_{3} | = 2$ . We may assume that every vertex has a similar distribution of edges. That is, we may assume that the edges out of each vertex fall into color classes of size 4, 4, and 2, since otherwise we could apply a previous case by making a different choice of $v$ .

Let $V (X_{1}) = {a, b, c, d}$ so that $a b$ and $c d$ are green and $b c$ blue. Let $V (X_{2}) = {p, q, r, s}$ so that $p q$ and $r s$ are green and $q r$ red. We are guaranteed the existence of these paths by Lemma 1. Lastly, let $V (X_{3}) = {x, y}$ . As in the previous subcase, we will begin with one edge and show that the choice of color for that edge fully determines the rest of the coloring.

Consider the set of edges ${b q, b r, c q, c r}$ . At least one of these edges must be red, since otherwise a blue $K_{3}$ results. This scenario is entirely symmetrical with respect to these edges, so we are free to suppose that the edge $b q$ is red. We must then have the following:

$b r$ must be blue, otherwise $G [{b, q, r}]$ is a red $K_{3}$ .
$b p$ must be red, otherwise $(b, p, q, b)$ is a proper $C_{3}$ .
$a q$ must be red, otherwise $(a, b, q, a)$ is a proper $C_{3}$ .
$a p$ must be red, otherwise $(a, b, p, a)$ is a proper $C_{3}$ .
$a r$ must be blue, otherwise $G [{a, q, r}]$ is a red $K_{3}$ .
$c r$ must be red, otherwise $G [{b, c, r}]$ is a blue $K_{3}$ .
$c q$ must be blue, otherwise $G [{c, q, r}]$ is a red $K_{3}$ .
$d r$ must be red, otherwise $(c, d, r, c)$ is a proper $C_{3}$ .
$c s$ must be red, otherwise $(c, s, r, c)$ is a proper $C_{3}$ .
$d s$ must be red, otherwise $(c, d, s, c)$ is a proper $C_{3}$ .
$b s$ must be blue, otherwise $(b, r, s, b)$ is a proper $C_{3}$ .
$c p$ must be blue, otherwise $(c, p, q, c)$ is a proper $C_{3}$ .
$d p$ must be blue, otherwise $(c, d, p, c)$ is a proper $C_{3}$ .
$d q$ must be blue, otherwise $(c, d, q, c)$ is a proper $C_{3}$ .
$a s$ must be blue, otherwise $(a, b, s, a)$ is a proper $C_{3}$ .

It then follows that the remaining edges within $X_{1}$ are all blue to avoid proper $3$ -cycles in $(a, d, q, a)$ , $(a, c, p, a)$ , and $(b, d, s, b)$ . Similarly, the remaining edges within $X_{2}$ are all red to avoid proper $3$ -cycles in $(p, a, s, p)$ , $(p, c, r, p)$ , and $(q, d, s, q)$ . Thus, $X_{1} + X_{2}$ must be colored as shown in Figure 3 in order to avoid both monochrome $K_{3}$ and proper $C_{3}$ .

Figure 3. Coloring of $X_{1} + X_{2}$ when $| X_{1} | = | X_{2} | = 4$ and edge $b q$ is red. Solid edges are red, dashed edges blue, and bold edges green.

Since the remaining edges out of $X_{1}$ can only be red or green, each vertex of $X_{1}$ must have one red edge and one green edge into $X_{3}$ , otherwise the color classes would not have the correct number of edges. Similarly, each vertex of $X_{2}$ must have one blue edge and one green edge into $X_{3}$ . (Recall, we may assume that every vertex has two edges of one color, and four each of the two remaining colors.) Specifically, exactly one of the edges in ${d x, d y}$ must be red, and the other green. Similarly, exactly one of the edges in ${s x, s y}$ must be blue and the other green.

Finally, consider the edge $x y$ in $X_{3}$ . This edge cannot be blue, for then $(d, x, y, d)$ would be a proper $C_{3}$ . Neither can it be red, for then $(s, x, y, s)$ would be a proper $C_{3}$ . This is a contradiction.

We have shown that $| X_{1} |$ cannot take on any value between $4$ and $10$ . But since it must take on one of these values, we have arrived at a contradiction. Therefore $P R (K_{3}, C_{3}) \leq 11$ .

We conclude that $P R (K_{3}, C_{3}) = 11$ .

We now move on to the result for $C_{5}$ .

Theorem 2. $P R (K_{3}, C_{5}) = 7$ .

Proof. We first exhibit a critical coloring on $K_{6}$ that contains neither a monochrome $K_{3}$ nor a properly colored $C_{5}$ . To construct this coloring, consider $K_{6}$ as $K_{5} + K_{1}$ . Decompose the $K_{5}$ subgraph into two Hamiltonian cycles, and color one cycle red and the other blue. Color the remaining edges (those between the $K_{5}$ and $K_{1}$ subgraphs) green. This coloring clearly contains no monochrome $K_{3}$ : the red and blue subgraphs are each copies of $C_{5}$ , while the green subgraph is the star $K_{1, 5}$ . On the other hand, any 5-cycle in the graph either contains the $K_{1}$ vertex or it does not. If it does, then it must contain adjacent green edges. If it does not, then it contains only red and blue edges. But $C_{5}$ cannot be properly colored with only two colors, so the graph contains no proper $C_{5}$ . Thus $P R (K_{3}, C_{5}) \geq 7$ .

Figure 4. This coloring on $K_{6}$ shows that $P R (K_{3}, C_{5}) \geq 7$ .

We next show that $P R (K_{3}, C_{5}) \leq 7$ . Let $G$ be a $3$ -edge-colored copy of $K_{7}$ containing neither a monochrome $K_{3}$ nor a properly colored $C_{5}$ . We show that this assumption produces a contradiction. Let $v$ be a vertex of $G$ with maximal color degree, and let $X_{1}$ , $X_{2}$ , and $X_{3}$ be the subgraphs of $G - v$ so that each $X_{i}$ is joined to $v$ entirely by edges of the same color. We will assume that $| X_{1} | \geq | X_{2} | \geq | X_{3} |$ and that $X_{1}$ , $X_{2}$ , and $X_{3}$ are joined to $v$ by red, blue, and green edges, respectively. These assumumptions can can always be satisfied by a relabeling of colors. Since $| X_{1} | + | X_{2} | + | X_{3} | = | G - v | = 6$ , the possible orders of these subgraphs must correspond to the three-part integer partitions of 6. We consider the possible cases in order of decreasing $| X_{1} |$ .

Case 1. Suppose that $| X_{1} | = 6$ . Then $X_{1}$ contains a 2-edge-colored $K_{6}$ . It follows that $G$ must contain a monochrome $K_{3}$ , since $R (K_{3}, K_{3}) = 6$ . This is a contradiction.

Case 2. Suppose that $| X_{1} | = 5$ . Then, without loss of generality, $| X_{2} | = 1$ . By Lemma 2 the subgraph $X_{1}$ must be decomposed into Hamiltonian cycles of different colors (blue and green) to avoid a monochrome $K_{3}$ . Let $V (X_{1}) = {a, b, c, d, e}$ so that the blue cycle is $(a, b, c, d, e, a)$ and the green cycle $(a, c, e, b, d, a)$ . Let $V (X_{2}) = {p}$ .

Note that for each vertex in $X_{1}$ , there is a proper $P_{4}$ in $G - p$ beginning at $v$ and ending on that vertex, whose final edge is blue. In alphabetical order of final vertex, $(v, c, e, a)$ , $(v, d, a, b)$ , $(v, a, d, c)$ , $(v, c, e, d)$ , and $(v, a, d, e)$ are proper such paths.

Then the edge $a p$ must be blue to avoid a proper $C_{5}$ ; choosing red or green yields a proper $C_{5}$ in $(v, c, e, a, p, v)$ . But the same consideration applies to every vertex of $X_{1}$ , so every edge out of $X_{1}$ into $X_{2}$ must be blue. But this yields a monochrome $K_{3}$ , such as $G [{a, b, p}]$ , so this is impossible. This case is illustrated in Figure 5.

Figure 5. The coloring that results if $| X_{1} | = 5$ in the proof of Theorem 1. This clearly contains a monchrome $K_{3}$ , contrary to our assumption.

Case 3. Suppose that $| X_{1} | = 4$ . Then there are two possibilities.

Subcase 3.1. . Suppose that $| X_{2} | = 2$ . By Lemma 1, $X_{1}$ contains a proper $P_{4}$ that begins and ends with blue edges. Let $V (X_{1}) = {a, b, c, d}$ , so that $(a, b, c, d)$ is the proper $P_{4}$ , and $V (X_{2}) = {p, q}$ . Note that $p q$ is not blue, for then $G [{p, q, v}]$ is a blue $K_{3}$ .

Consider the edges in ${a p, a q, d p, d q}$ . If any one of these edges is not blue, then a proper $C_{5}$ results. Note that these are symmetrically situated, so we may consider just one. Suppose that $d p$ were not blue. Then $(v, b, c, d, p, v)$ would be a proper $C_{5}$ . So indeed, each of the four edges indicated must be blue. But then $a d$ must be green to avoid a blue $K_{3}$ in $G [{a, d, q}]$ . But now a proper $C_{5}$ cannot be avoided, since $(v, a, d, p, q, v)$ is a proper $C_{5}$ . So this subcase is impossible.

Subcase 3.2.. Suppose that $| X_{2} | = | X_{3} | = 1$ . Again, by Lemma 1, $X_{1}$ contains a proper $P_{4}$ that begins and ends with blue edges. Let $V (X_{1}) = {a, b, c, d}$ , so that $(a, b, c, d)$ is the proper $P_{4}$ , and let $V (X_{2}) = {p}$ and $V (X_{3}) = {x}$ . Consider the edges $b x$ and $c x$ . If either of these edges is not green, then a proper $C_{5}$ results, namely either of $(v, a, b, c, x, v)$ or $(v, d, c, b, x, v)$ . But they also cannot both be green, since then $G [{b, c, x}]$ is a green $K_{3}$ . So this subcase is also impossible.

Case 4. Suppose that $| X_{1} | = 3$ . There are two possibilites. Either $| X_{2} | = 3$ or $| X_{2} | = 2$ and $| X_{3} | = 1$ .

Subcase 4.1.. Suppose $| X_{2} | = 3$ . Let $V (X_{1}) = {a, b, c}$ and $V (X_{2}) = {p, q, r}$ . Note that $X_{1}$ and $X_{2}$ are $2$ -edge-colored copies of $K_{3}$ not containing a monochrome $K_{3}$ , so each contains a proper $P_{3}$ . We may assume that $a b$ is green and $b c$ blue. Then $c r$ must be blue, otherwise $(v, a, b, c, r, v)$ is a proper $C_{5}$ . But note that $(r, q, p)$ is a proper $P_{3}$ with no blue edges. It follows that $(v, c, r, q, p, v)$ is a proper $C_{5}$ . So $c r$ cannot be blue. Hence, $c r$ must be both blue and not blue, a contradiction.

Subcase 4.2.. Suppose that $| X_{2} | = 2$ and $| X_{3} | = 1$ . Let $V (X_{2}) = {p, q}$ and $V (X_{3}) = {x}$ . Note that $X_{1}$ must contain a proper $P_{3}$ since it does not contain a monochrome $K_{3}$ . We may assume that $a b$ is blue and $b c$ green. But then,

$c x$ must be green, otherwise $(v, a, b, c, x, v)$ is a proper $C_{5}$ .
$b x$ is red or blue, otherwise $G [{b, c, x}]$ would be a green $K_{3}$ .
$a p$ must be blue, otherwise $(v, c, b, a, p, v)$ is a proper $C_{5}$ .
$b p$ is red or green, otherwise $G [{a, b, p}]$ is a blue $K_{3}$ .

Now consider $a c$ . This edge cannot be blue, for then $(v, a, c, b, x, v)$ is a proper $C_{5}$ . But neither can this edge be green, for then $(v, c, a, b, p, v)$ is a proper $C_{5}$ . Since this edge must be either blue or green, this is a contradiction.

Case 5. Suppose that $| X_{1} | = | X_{2} | = | X_{3} | = 2$ . Let $V (X_{1}) = {a, b}$ , $V (X_{2}) = {p, q}$ , and $V (X_{3}) = {x, y}$ . Since we assumed that $v$ has maximal color degree, it follows that every vertex of $G$ has the same number of edges of each color, namely 2. There are two subcases.

Subcase 5.1.. Suppose that two of the edges in ${a b, p q, x y}$ share a color. Without loss of generality, suppose that $a b$ and $x y$ are both blue. In that case, $a x$ must be blue, since otherwise $(v, b, a, x, y, v)$ is a proper $C_{5}$ . Since $a y$ , $b x$ , and $b y$ are symmetrically situated, they must all be blue as well. But then $G [{a, b, x}]$ is a blue $K_{3}$ , a contradiction.

Subcase 5.2.. Suppose that each of $a b$ , $p q$ , and $x y$ are different colors. Without loss of generality, suppose $a b$ is blue. Then $p q$ must be green and $x y$ must be red. Note that each of vertices $a$ and $b$ must be incident to two green edges, as we established at the beginning of this case. The vertices of $X_{2}$ and $X_{3}$ each have one green edge already. Since every vertex must be incident to two green edges, it follows that there is a green edge out of $X_{1}$ to each vertex in $X_{2}$ and $X_{3}$ . But this always produces a proper $C_{5}$ . Since this configuration is symmetric, it suffices to check one case. Indeed, if $a x$ is green, then $(v, b, a, x, y, v)$ is a proper $C_{5}$ . This is a contradiction.

We have shown that $| X_{1} |$ cannot take on any of its possible values, and thus arrived at a contradiction. It follows that a $3$ -edge-colored $K_{7}$ must contain either a monochrome $K_{3}$ or a properly colored $C_{5}$ , so $P R (K_{3}, C_{5}) \leq 7$ . Since we already showed that $P R (K_{3}, C_{5}) \geq 7$ , we conclude that $P R (K_{3}, C_{5}) = 7$ .

4. Concluding Remarks

These two theorems further the determination of the proper Ramsey number of $K_{3}$ against $C_{n}$ . We add the small odd cycles $C_{3}$ and $C_{5}$ to the even cycles treated by Olejniczak in [2]. There are only five remaining cases: $C_{7}$ , $C_{9}$ , $C_{11}$ , $C_{13}$ , and $C_{15}$ . Since the three color Ramsey number $R (K_{3}, K_{3}, K_{3}) = 17$ (see [6]), any $3$ -edge-colored copy of $K_{17}$ necessarily contains a monochrome $K_{3}$ , so any $3$ -edge-colored graph large enough to contain a proper $C_{17}$ necessarily contains a monochrome $K_{3}$ already. We may therefore stop at $C_{15}$ . Thus, finding these last five values would complete the determination of $P R (K_{3}, C_{n})$ .

Conflict of Interest

There was no conflict of interest in this study.

References:

English, S., Johnston, D., Olejniczak, D. and Zhang, P., 2017. Proper Ramsey numbers of graphs. Journal of Combinatorial Mathematics and Combinatorial Computing, 101, pp.281-299.[Google Scholor]
Olejniczak, D., 2019. Variations in ramsey theory. Ph.D. Thesis. Western Michigan University, Kalamazoo, MI.[Google Scholor]
Eroh, L.L., 2000. Rainbow ramsey numbers. Ph.D. Thesis. Western Michigan University, Kalamazoo, MI.[Google Scholor]
Chartrand, G. and Zhang, P., 2021. New directions in Ramsey theory. Discrete Mathematics Letters, 6, pp.84-96.[Google Scholor]
Chartrand, G. and Zhang, P., 2012. A first course in graph theory. Dover Publications, Garden City, NY.[Google Scholor]
Radziszowski, S., 2011. Small ramsey numbers. The Electronic Journal of Combinatorics, 1000, pp.DS1-Aug.[Google Scholor]

[1] English, S., Johnston, D., Olejniczak, D. and Zhang, P., 2017. Proper Ramsey numbers of graphs. Journal of Combinatorial Mathematics and Combinatorial Computing, 101, pp.281-299.[Google Scholor]

[2] Olejniczak, D., 2019. Variations in ramsey theory. Ph.D. Thesis. Western Michigan University, Kalamazoo, MI.[Google Scholor]

[3] Eroh, L.L., 2000. Rainbow ramsey numbers. Ph.D. Thesis. Western Michigan University, Kalamazoo, MI.[Google Scholor]

[4] Chartrand, G. and Zhang, P., 2021. New directions in Ramsey theory. Discrete Mathematics Letters, 6, pp.84-96.[Google Scholor]

[5] Chartrand, G. and Zhang, P., 2012. A first course in graph theory. Dover Publications, Garden City, NY.[Google Scholor]

[6] Radziszowski, S., 2011. Small ramsey numbers. The Electronic Journal of Combinatorics, 1000, pp.DS1-Aug.[Google Scholor]

Contents

Journal of Combinatorial Mathematics and Combinatorial Computing