% EJC papers *must* begin with the following two lines. 
\documentclass[12pt]{article}
\usepackage{e-jc}

% Please remove all other commands that change parameters such as
% margins or pagesizes.

% only use standard LaTeX packages
% only include packages that you actually need

% we recommend these ams packages
\usepackage{amsthm,amsmath,amssymb}

% we recommend the graphicx package for importing figures
\usepackage{graphicx}

% use this command to create hyperlinks (optional and recommended)
\usepackage[ps2pdf=true,colorlinks=true,citecolor=black,linkcolor=black,urlcolor=blue]{hyperref}

% use these commands for typesetting doi and arXiv references in the bibliography
\newcommand{\doi}[1]{\href{http://dx.doi.org/#1}{\texttt{doi:#1}}}
\newcommand{\arxiv}[1]{\href{http://arxiv.org/abs/#1}{\texttt{arXiv:#1}}}
\newcommand{\gn}[1]{#1}
\newcommand{\flr}[1]{\left\lfloor #1 \right\rfloor}
\newcommand{\ceil}[1]{\left\lceil #1 \right\rceil}
\newcommand{\pp}{\prime \prime}

\DeclareGraphicsRule{*}{eps}{*}{}
\input{epsf}

% all overfull boxes must be fixed; 
% i.e. there must be no text protruding into the margins


% declare theorem-like environments
\theoremstyle{plain}
\newtheorem{theorem}{Theorem}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{fact}[theorem]{Fact}
\newtheorem{observation}[theorem]{Observation}
\newtheorem{claim}[theorem]{Claim}
\newtheorem{case}{Case}
\newtheorem{subcase}{Subcase}[case]

\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{conjecture}[theorem]{Conjecture}
\newtheorem{open}[theorem]{Open Problem}
\newtheorem{problem}[theorem]{Problem}
\newtheorem{question}[theorem]{Question}

\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}
\newtheorem{note}[theorem]{Note}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% if needed include a line break (\\) at an appropriate place in the title

\title{\bf The structure of colored complete graphs free of proper cycles}

% input author, affilliation, address and support information as follows;
% the address should include the country, and does not have to include
% the street address 

\author{Vincent Coll\\
\small Department of Mathematics\\[-0.8ex]
\small Lehigh University\\[-0.8ex] 
\small Bethlehem, PA, U.S.A.\\
\small\tt vec208@lehigh.edu\\
\and
Colton Magnant\\
\small Department of Mathematical Sciences\\[-0.8ex]
\small Georgia Southern University\\[-0.8ex]
\small Statesboro, GA, U.S.A.\\
\small\tt cmagnant@georgiasouthern.edu
\and
Kathleen Ryan\\
\small Department of Mathematics\\[-0.8ex]
\small Lehigh University\\[-0.8ex] 
\small Bethlehem, PA, U.S.A.\\
\small\tt kmr207@lehigh.edu\\
\and
}

% \date{\dateline{submission date}{acceptance date}\\
% \small Mathematics Subject Classifications: comma separated list of
% MSC codes available from http://www.ams.org/mathscinet/freeTools.html}

\date{\dateline{Jan 1, 2012}{Jan 2, 2012}\\
\small Mathematics Subject Classifications: 05C15, 05C38}

\begin{document}

\maketitle

% E-JC papers must include an abstract. The abstract should consist of a
% succinct statement of background followed by a listing of the
% principal new results that are to be found in the paper. The abstract
% should be informative, clear, and as complete as possible. Phrases
% like "we investigate..." or "we study..." should be kept to a minimum
% in favor of "we prove that..."  or "we show that...".  Do not
% include equation numbers, unexpanded citations (such as "[23]"), or
% any other references to things in the paper that are not defined in
% the abstract. The abstract will be distributed without the rest of the
% paper so it must be entirely self-contained.

\begin{abstract}
For a fixed integer $m$, we consider edge colorings of complete graphs which contain no properly edge colored cycle $C_{m}$ as a subgraph.  Within colorings free of these subgraphs, we establish \gn{a} global structure by bounding the number of colors that can induce a spanning and connected subgraph.  In the case of small cycles, namely $C_4,C_5$, and $C_6$, we show that our bounds are sharp.

  % keywords are optional
  \bigskip\noindent \textbf{Keywords:} proper coloring; forbidden subgraph; monochromatic subgraph
\end{abstract}

\section{Introduction}

This work considers edge colorings of complete graphs $K_{n}$ on $n$ vertices which contain no properly edge colored cycle of length $m$ as a subgraph, where $m \geq 3$ is an integer.  Within edge colorings free of a properly colored $C_{m}$, we establish a global structure on the coloring by bounding the number of colors that can induce a spanning and connected subgraph.  For small $m$, namely for $C_4,C_5$, and $C_6$, we show that our bounds are the best possible. We tacitly assume that by \emph{coloring}, we mean a partition of $E(K_{n})$ into parts called \emph{color classes}.  A subgraph is called \emph{rainbow} if all of its edges are colored distinctly while a subgraph is called \emph{proper} (elsewhere called ``alternating'' \cite{BG09}) if no two adjacent edges receive the same color.

This project is primarily motivated by the following result of Gy{\'a}rf{\'a}s et al, who translated the work of Gallai, recasting his work on oriented graphs to be sensible in the context of graph coloring (see~\cite{G67} and~\cite{GS04}).

\begin{theorem}[Gallai \cite{G67}, Gy{\'a}rf{\'a}s et al. \cite{GS04}]\label{GallaiDecomp}
A coloring of $K_{n}$ is rainbow triangle free if and only if there exists a partition of the vertices into at least two non-empty parts such that between each pair of parts, all edges have a single color, between the parts in general, the edges come from only two colors and within each part, the edges are colored to avoid rainbow triangles.
\end{theorem}

This theorem is a strong structural result demonstrating how restricted the structure of an edge colored complete graph $K_n$ is if its coloring is known to be rainbow triangle free.  Theorem~\ref{GallaiDecomp} has naturally led to an investigation of the structure of colorings of $K_n$ which are free of rainbow subgraphs other than triangles (see~\cite{FGMS11} and~\cite{FM11}).

In this work, we generalize the rainbow triangle free results, but do so by investigating colorings of $K_n$ which are free of proper cycles of length longer than three.  For a coloring $G$ of $K_n$, we let $G^{i}$ denote the subgraph of $G$ induced on color $i$, and we say that color $i$ is \emph{spanning} and \emph{connected} if $G^i$ is a spanning and connected subgraph of $K_n$.  The following theorem suggests the form of the structural results that we seek.

%Our strategy involves analyzing the number of spanning and connected colors which force the existence of a proper cycle of a given length.  The impetus for this strategy extends from the following theorem.

\begin{theorem}[Gallai \cite{G67}, Gy{\'a}rf{\'a}s et al. \cite{GS04}]\label{gallai}
If a coloring of $K_{n}$ is rainbow triangle free, then there are at most two colors which are spanning and connected.
\end{theorem}

This theorem shows that a coloring of $K_{n}$ with three or more spanning and connected colors contains a rainbow triangle.  In the translation of Gallai's results, Theorem~\ref{gallai} was the main tool in the proof of Theorem~\ref{GallaiDecomp}.  Along these lines, our goal is to obtain analogs of Theorem~\ref{gallai} for proper-$C_m$ free colorings of $K_n$ so as to find structural results as strong as Theorem~\ref{GallaiDecomp} for such graphs.  In Sections~\ref{Section:C4},~\ref{Section:C5}, and~\ref{Section:C6}, we determine the number of spanning and connected colors which respectively force the existence of a proper $C_4$, $C_5$, or $C_6$.  In Section~\ref{Section:General}, we obtain more general results by finding upper and lower bounds for the number of spanning and connected colors required to ensure the existence of a proper $C_m$, for $m \geq 4$.

Note that a survey of Gallai's results, as well as many others related to rainbow subgraphs of complete graphs, can be found in~\cite{FMO10} with an updated version maintained at~\cite{Survey}.

When it is convenient, we use names of colors like ``red'' or ``green''.

% ---------------------
\section{Proper-$C_{4}$ free Colorings} \label{Section:C4}
% ---------------------
The first result of this section provides some structure to colorings of $K_n$ that are free of proper even cycles $C_{2m}$.  When $m=2$, this result provides a first insight into the structure of proper-$C_4$ free colorings.

\begin{theorem}\label{diam2}
For $m \geq 2$, if $G$ is a proper-$C_{2m}$ free coloring of $K_{n}$, then the sum of the diameters of the components of $G^{i}$ is at most $2(m - 1)$.  In particular, when $m = 2$, if $G$ is a proper-$C_4$ free coloring of $K_{n}$, then with the exception of isolated vertices, each color in $G$ is connected with diameter at most two.
\end{theorem}

\begin{proof}
This proof is by contradiction.  Consider a coloring of $K_{n}$ with no proper $C_{2m}$ and suppose that $G^{1}$ is \gn{spanning and} connected but that there exist vertices $a$ and $b$ at distance at least $2m - 1$ in $G^{1}$.  Without loss of generality, choose $a$ and $b$ so that the distance between them is exactly $2m - 1$.  Let $P$ be a shortest path from $a$ to $b$.  Since the path $P$ is a shortest $a-b$ path in color $1$, all chords of this path must not have color $1$.  Label the vertices of $P$ in order as $a = a_{1}, a_{2}, \dots, a_{2m} = b$.  Indices will be considered modulo $2k$.  

Now, suppose $m$ is even.  Let $C$ be a proper cycle constructed \gn{from $P$} as follows: For $i \geq 0$, consider the segment $a_{4i + 1}a_{4i + 2}a_{4i + 3}a_{4i + 4}a_{4i + 5}$.  This segment is replaced by the path segment $P_{i} = a_{4i + 1}a_{4i + 2}a_{4i + 4}a_{4i + 3}a_{4i + 5}$.  \gn{By construction, this path segment $P_{i}$ is proper.}  If this process is repeated for all $i \leq m/2 - 1$, it produces a proper $C_{2m}$ for a contradiction.  Note that the case when $i = m/2 - 1$ produces the proper segment $a_{2m - 3}a_{2m - 2}a_{2m}a_{2m - 1}a_{1}$.

If $m$ is odd, we employ a similar process: For $i \leq (m - 1)/2 - 1$, we make the same switches.  \gn{For the} final segment, \gn{when $i = (m - 1)/2$,} we use is $a_{2m - 1}a_{2m}a_{1}$ to complete a proper $C_{2m}$ for a contradiction.

A similar argument within and between components shows the result holds when $G^{i}$ is disconnected but the sum of the diameters of the components is greater than $2(m - 1)$.  \end{proof}

\gn{Note that a result like Theorem~\ref{diam2} does not hold in general for proper-$C_{2m+1}$ free colorings of $K_{n}$.  Consider a red path on $n - 2$ vertices and a single isolated edge colored in green.  Color all other edges in this graph blue to yield a coloring of $K_{n}$.  This coloring contains no properly colored odd cycle of any length since every other edge in any proper cycle $C$ must be blue and thus $C$ must be even.  On the other hand, the subgraph induced on the red edges in this coloring has diameter $n - 3$, thus demonstrating that we can find colorings of $K_{n}$ with no proper cycles of odd length and with at least one color with large diameter.}  Applying Theorem~\ref{diam2}, we obtain the analog of Theorem~\ref{gallai} for proper-$C_4$ free colorings of $K_n$.  The next theorem implies that any coloring containing two or more spanning and connected colors forces the existence of a proper $C_4$.

\begin{theorem}\label{C4Discon}
For $n \geq 4$, if $G$ is a proper-$C_{4}$ free coloring of $K_{n}$, then $G$ has at most one spanning and connected color.
\end{theorem}

\begin{proof}
\gn{The proof is by induction on $n$.}  First, suppose $n = 4$.  The only way for two colors to be \gn{spanning and} connected in a colored $K_{4}$ is to have a $P_{4}$ in color $1$ and a $P_{4}$ (the complement of the first $P_{4}$) in color $2$.  Then neither color induces a graph of diameter at most two, contradicting Theorem~\ref{diam2}.

Now, suppose the result holds for colorings of $K_{n - 1}$, and let $G$ be a coloring of $K_{n}$.  Suppose colors $1$ and $2$ are both \gn{spanning and} connected in $G$.  By induction, if we remove any vertex $v$, we are left with at most one \gn{spanning and} connected color, say color $1$.  Then, in $G^{2}$, the vertex $v$ is a cut vertex.  Since the diameter of $G^{2}$ is at most two by Theorem~\ref{diam2}, the vertex $v$ must be adjacent to all of $G \setminus \{v\}$ in color $2$.  This means that color $2$ is the only \gn{spanning and} connected color in $G$.  \end{proof}

This theorem establishes that, in a proper-$C_{4}$ free coloring of a complete graph, there is at most one spanning and connected color.  On the other hand, there may not even be one such color, as seen in the following example:  Consider three sets $A_{1}, A_{2}$, and $A_{3}$, each of order $n/3$ (see Figure~\ref{Figure:Triangle}).  Color all edges contained in each set $A_{i}$ with color $i$ and all edges from $A_{i}$ to $A_{i + 1}$ with color $i$ where indices are taken modulo $3$.  This example is proper-$C_{4}$ free but has no spanning and connected color.

\begin{figure}[ht!]
\begin{center}
% \epsfxsize 2in \epsfbox{TriangleFig.1}
 \epsfxsize 2in \epsfbox{TriangleFig.2}
 \caption{Coloring with no proper $C_{4}$ and no spanning and connected color \label{Figure:Triangle}}
\end{center}
\end{figure}


% ---------------------
\section{Proper-$C_{5}$ free Colorings} \label{Section:C5}
% ---------------------

We now obtain the analog of Theorem~\ref{gallai} for proper-$C_5$ free colorings of $K_n$.  Theorem~\ref{C5Thm} shows that any coloring containing three or more spanning and connected colors forces the existence of a proper $C_5$.


\begin{theorem}\label{C5Thm}
For $n \geq 5$, if $G$ is a proper-$C_{5}$ free coloring of $K_{n}$, then $G$ has at most two spanning and connected colors.
\end{theorem}

\begin{proof}
The proof is by induction on $n$.  Suppose $G$ is a \gn{proper-$C_{5}$ free} coloring of $K_{n}$ for $n \geq 5$ in which at least $3$ colors, say colors $1$, $2$, and $3$, are \gn{spanning and} connected.  \gn{ For a base case, if} $n = 5$, each \gn{spanning and} connected color needs at least $n - 1 = 4$ edges so there cannot be three \gn{spanning and} connected colors on $e(K_{5}) = 10$ edges.  Thus, we may assume $n \geq 6$.  First, we show that the graph induced on each of colors $1$, $2$, and $3$ has small diameter.

\begin{claim}\label{C5DiamClaim}
The diameter of $G^{i}$ is at most three for all $i$.
\end{claim}

\begin{proof}
This proof is by contradiction.  Suppose the diameter of $G^{1}$ is at least four.  Then there exists an induced path $P = v_{1}v_{2}\dots v_{5}$ on $5$ vertices where the distance, in $G^{1}$, between $v_{1}$ and $v_{5}$ is four.  By combining colors, we may assume that there are at most two other colors, suppose $2$ and $3$, on the edges.  Our first goal is to show that there is only one color on the remaining edges in $G' = G[V(P)]$.

First, suppose color $3$ has only one edge $e$ in $G'$ and all remaining edges within $G[V(P)]$ have color $2$.  Regardless of the position of $e$, it is easy to construct a proper $C_{5}$ in this structure so each color $2$ and $3$ must have at least two edges in $G'$.  At least one of these colors, say color $2$, must be present on two disjoint edges.  Suppose $v_{1}v_{3}$ and $v_{2}v_{4}$ both have color $2$.  The case where $v_{1}v_{3}$ and $v_{2}v_{5}$ have color $2$ is similar and all other cases \gn{can be argued similarly}.  Now, the edge $v_{1}v_{5}$ must also have color $2$ since otherwise $v_{1}v_{3}v_{2}v_{4}v_{5}v_{1}$ forms a proper $C_{5}$.  Also $v_{3}v_{5}$ must have color $2$ since otherwise $v_{1}v_{2}v_{4}v_{3}v_{5}v_{1}$ gives a proper $C_{5}$.  Finally, if $c(v_{1}v_{4}) = c(v_{2}v_{5}) = 3$, then $v_{1}v_{4}v_{5}v_{2}v_{3}v_{1}$ yields a proper $C_{5}$ (here $c(e)$ denotes the color of the edge $e$).  Hence, there is at most one edge of color $3$, for a contradiction.  Thus, there are only two colors, say $1$ and $2$, on the edges of $G'$.

Since color $3$ is \gn{spanning and} connected, there exists a vertex $v \in G \setminus P$ such that $c(vv_{1}) = 3$.  \gn{It is easy to see that in order to avoid a proper $C_{5}$, all edges from $v$ to $P$ must have color $3$}.  Now since color $1$ is \gn{spanning and} connected, there is an edge of color $1$ from $v$ to a vertex $w \in G \setminus P$.  \gn{In particular, this means $n$ must be at least $7$.}  In order to avoid easily constructing a proper $C_{5}$, all edges from $w$ to $P$ must have color $1$, but this contradicts the assumption that the distance from $v_{1}$ to $v_{5}$ in $G^{1}$ is four.  \end{proof}

Continuing with the proof of Theorem~\ref{C5Thm}, suppose there exists a vertex $v$ such that $G \setminus \{v\}$ still has three \gn{spanning and} connected colors.  Then, by induction on $n$, there exists a proper $C_{5}$ in $G \setminus \{v\}$ and so also in $G$.  Thus, every vertex of $G$ is a cut vertex of $G^{i}$, for some $1 \leq i \leq 3$.  Let $S_{i}$ be the set of cut vertices of $G^{i}$ for all $i$.  \gn{For all $i$, since $G_{i}$ has diameter at most $3$ by Claim~\ref{C5DiamClaim}, it can be shown that} $S_{i}$ \gn{induces a complete graph} in color $i$.  

\gn{Suppose for a moment that $n \geq 7$.  Then $|S_{i}| \geq 3$ for some $i$, and without loss of generality, suppose $i = 1$.  Let $S_{1} = \{s_{1}, s_{2}, s_{3}, \dots \}$ and let $V_{i}$ be the set of vertices in $G \setminus S_{1}$ with only one edge in color $1$ to $S_{1}$, to $s_{i}$, for all $i$.  Note that $V_{i} \neq \emptyset$ for all $i$ since every vertex of $S_{1}$ must be a cut vertex of $G^{1}$.  The subgraph $H$ induced by  $S_{1} \cup V_{1} \cup V_{2} \cup \dots$ is shown Figure~\ref{Fig:TriAndPendants}.  

\begin{figure}[ht!]
\begin{center}
 \epsfbox{S1Fig.1}
 \caption{Graphs induced by each color \label{Fig:TriAndPendants}}
\end{center}
\end{figure}


\begin{claim}\label{Claim:allc1}All edges in $H$ have color $1$ or color $c\neq 1$. 
\end{claim}

\begin{proof}
This proof is also by contradiction.  In this proof, $v_i$ indicates any vertex in $V_i$.  Let $i,j,k$ be distinct indices.  Edges $s_iv_j$ and $v_jv_k$ have the same color because otherwise, $s_{i}v_{j}v_{k}s_{k}v_{i}s_{i}$ is a proper $C_5$.  This forces that all edges between $s_i, V_j,$ and $V_k$ have the same color but this color may depend on $i,j,k$.  Call this Fact (1).  To show all edges between $s_i, V_j,$ and $ V_k$ have the same color $c$ regardless of $i,j,k$, it suffices to show all edges between $V_i$ and $V_j$ and between $V_j$ and $V_k$ have the same color.  Assume this is not true.  There there are edges $v_iv_j$ and $v_jv_k$ which have different colors.  Then by Fact (1), $s_{i}v_{j}$ and $v_{j}s_{k}$ have different colors as well and so $v_{i}s_{i}v_{j}s_{k}v_{k}v_{i}$ is a proper $C_5$.  Thus, all edges between $V_i$ and $V_j$ and between $V_j$ and $V_k$ have the same color $c$ and we have just shown that all edges which are not color 1 and are not contained in some $V_i$ have the same color $c$.  Finally, we show all edges within $V_i$ have colors $1$ or $c$ as well.  Assume some edge $xy$ within $V_i$ has a color that is not $1$ or $c$.  Then for any $s_j$ where $j\neq i$ and $v_{j}s_{j}xys_{i}v_{j}$ is a proper $C_5$, a contradiction.  
\end{proof}


Again continuing with the proof of Theorem~\ref{C5Thm}, assume, without loss of generality, that $c=2$. Now, let $v_1 \in V_{1}$.  We know that $v_1$ has an edge of color $3$ to a vertex $u$ but by Claim~\ref{Claim:allc1}, we must have $u \in G \setminus H$.  Since $G^{1}$ has diameter at most $3$, $u$ has an edge in color $1$ to $S_{1}$ but since $u \notin V_{i}$ for any $i$, $u$ must have at least two edges in color $1$ to $S_{1}$.  That means $u$ must have at least one edge in color $1$ to $s_{i}$ where $i \neq 1$.  Without loss of generality, suppose $i = 2$.  Then $v_1us_{2}v_3s_{3}v_1$ is a proper $C_{5}$ for some vertex $v_3 \in V_{3}$, a contradiction.  This completes the proof for the case when $n\geq 7$.}

Finally, suppose $n = 6$.  In a coloring of $K_{6}$ with three spanning and connected colors, each color must use exactly five edges and form a tree.  By Claim~\ref{C5DiamClaim}, we know that each color has diameter at most three.  \gn{If one color has diameter $2$, then since it is also a tree, it is a spanning star and no other color is connected to the center of this star.}  Thus, we may assume each color induces a tree of diameter exactly three.  This means that each color induces one of the graphs in Figure~\ref{diam3trees}.

\begin{figure}[ht!]
\begin{center}
 \epsfbox{diamtrees.1}
 \caption{Graphs induced by each color \label{diam3trees}}
\end{center}
\end{figure}

In fact, since each vertex of $K_{6}$ has degree five and all three colors are spanning, every color must induce precisely the tree $T_{1}$.  Without loss of generality, \gn{we may assume color $1$ induces the tree $T_{1}$ shown and that} $v_{1}v_{5}$ has color $2$.  Then $v_{3}v_{5}$ also has color $2$ or else $v_{1}v_{2}v_{4}v_{3}v_{5}v_{1}$ forms a proper $C_{5}$.  Furthermore, $v_{1}v_{3}$ must also have color $2$ since otherwise $v_{1}v_{5}v_{2}v_{6}v_{3}v_{1}$ gives a proper $C_{5}$.  Now there is a triangle in color $2$, contradicting the fact that it must induce a copy of $T_{1}$.  This completes the proof of Theorem~\ref{C5Thm}.  \end{proof}

% ---------------------
\section{Proper-$C_{6}$ free Colorings} \label{Section:C6}
% ---------------------

\gn{In this section, we establish} an analog of Theorem~\ref{gallai} for proper-$C_6$ free colorings of $K_n$.  As in the case of proper-$C_5$ free colorings, \gn{Theorem~\ref{C6Thm}} similarly shows that any coloring with three or more spanning and connected colors forces the existence of a proper $C_6$.

%By Proposition~\ref{2colorscon}, it would take at least $3$ colors to imply the existence of a properly colored $C_{6}$.  As in the previous case, it turns out that this is again the case.

\begin{theorem}\label{C6Thm}
For $n \geq 6$, if $G$ is a proper-$C_{6}$ free coloring of $K_{n}$, then $G$ has at most two spanning and connected colors.
\end{theorem}

\begin{proof}
\gn{We show the claim is true for $n=6$ at the end of our proof. For $n>6$, our proof uses a minimal counterexample} but we first need some claims that will be extremely important in the proof.  Let $G$ be a proper-$C_{6}$ free coloring of $K_{n}$ with $n > 6$ and suppose, for a contradiction, that $G$ has at least three colors which induce \gn{spanning and} connected graphs but the result holds for smaller complete graphs.  \gn{This leads to the following immediate fact.}

\begin{fact}\label{Fact:cutvertex}
For every vertex $v \in G$, $G \setminus \{v\}$ contains at most two \gn{spanning and} connected colors.
\end{fact}

In particular if $G$ has $\ell \geq 3$ \gn{spanning and} connected colors, this means that every vertex is a cut vertex of at least $\ell - 2 \geq 1$ colors.

\begin{claim}\label{Claim:ConnectedCuts}
Within the subgraph induced on each \gn{spanning and} connected color, the graph induced on the cut vertices must be connected.
\end{claim}

\begin{proof}
The proof is by contradiction.  Suppose a monochromatic subgraph, say red, is \gn{spanning and} connected and contains two cut vertices $u$ and $v$ that are not adjacent in red (and not connected by a sequence of cut vertices).  Then the red subgraph, after removal of these two vertices, must have at least three components $A$, $B$, and $C$.  One such component, say $B$, must have at least one edge to both $u$ and $v$ while at least one other component, say $A$, must be adjacent to $u$ and another, say $C$, adjacent to $v$.  Since $n \geq 7$, at least one of these components must contain at least two vertices and so an edge $e$.  Suppose, without loss of generality, that $e \in A$ (the case where $e \in B$ is handled identically).  Then let $f$ be an edge from $B$ to $u$ and let $g$ be an edge from $C$ to $v$.  Then using the edges $e, f, g$, it is easy to produce a properly colored $C_{6}$ for a contradiction.  \end{proof}

For the statement of the next claim, we define a \emph{slim caterpillar} to be a graph consisting of two vertex disjoint stars each containing at least one edge with the addition of a single vertex adjacent only to the centers of the two stars.  The centers of the stars along with the added vertex are called the \emph{body} of the caterpillar.

\begin{claim}\label{Claim:3Cuts}
The graph induced on each \gn{spanning and} connected color has at most three cut vertices.  Moreover, if the graph induced on a color has three cut vertices, it must induce a slim caterpillar.
\end{claim}

\begin{proof}
Suppose the red subgraph has at least three cut vertices.  Within the red subgraph, by Claim~\ref{Claim:ConnectedCuts}, the cut vertices must induce a connected graph.  If there is a set $T$ of three cut vertices which induce a red connected graph, each with at least one red edge to a vertex that is not in $T$ (since vertices in $T$ are cut vertices, these neighbors must all be distinct), then using these three \gn{disjoint red} edges, one may easily produce a proper $C_{6}$.  Thus, if there are three cut vertices \gn{of the red subgraph}, one must only have red edges to the other two, thereby forcing the graph induced on the red edges to be a slim caterpillar.

Next suppose that there are at least four cut vertices of the subgraph induced on the red edges.  Let $C = \{u, v, w, x\}$ be four of the cut vertices which themselves induce a red connected graph.  Thus, we may assume two of the vertices, say $v$ and $w$, only have edges to $u$ and/or $x$.  Since each of these vertices is a cut vertex of the red subgraph and they induce a connected subgraph themselves, this means $C$ must induce a red path, say $uvwx$.  Let $e$ be an edge from $u$ to $G \setminus C$ and $f$ be an edge from $x$ to $G \setminus C$.  Such edges exist since these are cut vertices.  Then using $e$, $f$, and the edge $vw$ we may again easily produce the desired properly colored $C_{6}$.  \end{proof}

First, suppose $n \geq 10$.  By Fact~\ref{Fact:cutvertex}, every vertex of $G$ is a cut vertex of some \gn{spanning and} connected color but by Claim~\ref{Claim:3Cuts}, each \gn{spanning and} connected color has at most three cut vertices.  This means that there must be at least $\ceil{ \frac{n}{3}} \geq 4$ \gn{spanning and} connected colors in $G$.  By Fact~\ref{Fact:cutvertex} again, every vertex of $G$ is a cut vertex for at least $\ceil{\frac{n}{3}} - 2$ colors but since each color still has at most three cut vertices, there must be at least
$$
\ceil{ \frac{n \left(\ceil{ \frac{n}{3} } - 2 \right)}{3} } \geq \frac{2n}{3}
$$
\gn{spanning and} connected colors.  This is clearly a contradiction since each \gn{spanning and} connected color requires at least $n - 1$ edges to be connected.  This concludes the proof \gn{when $n \geq 10$} so it remains to show that the result holds for $6 \leq n \leq 9$.

If $7 \leq n \leq 9$ and there are at least four \gn{spanning and} connected colors, then the above argument holds for a contradiction.  Since each color has at most three cut vertices and every vertex is a cut, there must then be exactly three \gn{spanning and} connected colors.

We break the remainder of the proof into cases based on the value of $n$.

\setcounter{case}{0}
\begin{case}
$8 \leq n \leq 9$.
\end{case}

By Claim~\ref{Claim:3Cuts}, two of these colors induce body-disjoint slim caterpillars.  Up to \gn{relabeling}, these must induce the graph in Figure~\ref{Figure:2Pillars} where $\{v_{1}, v_{2}, v_{3}\}$ is the body of the caterpillar on the thin edges representing color $1$, and $\{v_{4}, v_{5}, v_{6}\}$ is the body of the caterpillar on the thick edges representing color $2$.  Note that the dotted edges may not all be the same color but certainly must not be either color $1$ or $2$.
Regardless of the colors of the dotted edges, the cycle $v_{5}v_{6}v_{4}v_{1}v_{3}v_{2}v_{5}$ must be a proper $C_{6}$ for a contradiction.

\begin{figure}[ht!]
\begin{center}
% \epsfbox{TwoPillars.2}
 \epsfbox{TwoPillars.1}
 \caption{If there are two slim caterpillars \label{Figure:2Pillars}}
\end{center}
\end{figure}


\begin{case}
$n = 7$.
\end{case}

This case is proven by case analysis similar to classical forbidden subgraph arguments.  As observed above, there can only be three colors that are \gn{spanning and} connected and one of these colors, say red, must induce a slim caterpillar.  Then suppose blue and green are the other two \gn{spanning and} connected colors, each having at least two cut vertices.  Let $v_{1}, v_{2}, v_{3}$ be the body of the red caterpillar.

First, suppose each of $v_{1}$ and $v_{3}$ has exactly two red neighbors other than $v_{2}$.  Let $v_{4}, v_{5}$ be the red neighbors of $v_{1}$ and let $v_{6}, v_{7}$ be the red neighbors of $v_{2}$.  Since we have assumed the cycle $v_{1}v_{3}v_{a}v_{b}v_{i}v_{j}v_{1}$ where $\{a, b\} = \{6, 7\}$ and $\{i, j\} = \{4, 5\}$ is not proper, we \gn{may assume} that the edge $v_{b}v_{i}$ must be the same color as either $v_{a}v_{b}$ or $v_{i}v_{j}$.  On the other hand, if all edges within $\{v_{4}, v_{5}, v_{6}, v_{7}\}$ have the same color, say blue, then \gn{by Claim~\ref{Claim:ConnectedCuts},} it is impossible for two of these vertices to be cut vertices of the subgraph induced on green edges.  Thus, we may assume, without loss of generality, that $v_{4}v_{5}$ is green and that $v_{5}v_{6}$ and $v_{6}v_{7}$ are both blue.

By looking at the cycle $v_{4}v_{5}v_{6}v_{3}v_{1}v_{2}v_{4}$, the edge $v_{2}v_{4}$ must be green to avoid a proper $C_{6}$.  Also using the cycle $v_{4}v_{5}v_{1}v_{3}v_{7}v_{2}v_{4}$, the edge $v_{7}v_{2}$ must be green.  From the cycle $v_{6}v_{7}v_{2}v_{3}v_{5}v_{1}v_{6}$, the edge $v_{1}v_{6}$ must be blue.  From the cycle $v_{4}v_{1}v_{3}v_{3}v_{7}v_{5}v_{4}$, we get $v_{7}v_{5}$ must be green.  Finally, from the cycle $v_{6}v_{8}v_{5}v_{1}v_{3}v_{2}v_{6}$, the edge $v_{2}v_{6}$ is blue so, since green is \gn{spanning and} connected, $v_{4}v_{6}$ must be green.  This gives a proper $C_{6}$ on the vertices $v_{4}v_{1}v_{3}v_{2}v_{7}v_{6}v_{4}$ for a contradiction.

Thus, we may assume one of $v_{1}$ or $v_{3}$, say $v_{1}$, has three red neighbors, say $v_{4}, v_{5}, v_{6}$.  Since three colors are \gn{spanning and} connected, $v_{1}$ must also have a blue edge and a green edge so suppose $v_{1}v_{3}$ is blue and $v_{1}v_{7}$ is green.  The vertex $v_{3}$ must have another blue edge since the blue graph is \gn{spanning and} connected so, without loss of generality, say $v_{3}v_{5}$ is blue.  Also $v_{3}$ needs a green edge so say $v_{3}v_{6}$ is green.  By considering the cycle $v_{1}v_{4}v_{2}v_{3}v_{6}v_{7}v_{1}$, we see that $v_{6}v_{7}$ must be green to avoid a proper $C_{6}$.

Suppose first that the edge $v_{5}v_{7}$ is blue.  Then the cycle $v_{1}v_{5}v_{7}v_{6}v_{2}v_{3}v_{1}$ must not be proper so $v_{2}v_{6}$ must be green.  Also the cycle $v_{1}v_{4}v_{3}v_{2}v_{5}v_{7}v_{1}$ must not be proper so $v_{2}v_{5}$ is blue.  If $v_{4}v_{6}$ is blue, then the cycle $v_{1}v_{4}v_{6}v_{5}v_{3}v_{7}v_{1}$ implies $v_{6}v_{5}$ is blue and since green is \gn{spanning and} connected, $v_{5}v_{4}$ must be green so $v_{1}v_{4}v_{5}v_{6}v_{7}v_{3}v_{1}$ is a proper $C_{6}$.  Thus, $v_{4}v_{6}$ must be green.  Since blue is \gn{spanning and} connected, $v_{5}v_{6}$ must be blue which means $v_{5}v_{4}$ must be green - again making $v_{1}v_{4}v_{5}v_{6}v_{7}v_{3}v_{1}$ a proper $C_{6}$.

Finally, suppose the edge $v_{5}v_{7}$ is green.  First, we will also assume $v_{4}v_{6}$ is green.  The cycle $v_{1}v_{4}v_{6}v_{5}v_{7}v_{3}v_{1}$ cannot be proper so $v_{5}v_{6}$ must also be green.  Since $v_{6}$ must have a blue edge, $v_{6}v_{2}$ must be blue.  Since the cycle $v_{1}v_{3}v_{7}v_{2}v_{6}v_{5}v_{1}$ is not proper, this shows that $v_{7}v_{2}$ must be blue but the cycle $v_{1}v_{4}v_{2}v_{6}v_{7}v_{3}v_{1}$ must also not be proper, showing that $v_{4}v_{2}$ must also be blue.  This implies that $v_{5}v_{2}$ must be green for $v_{2}$ to have a green edge but then $v_{1}v_{5}v_{2}v_{6}v_{7}v_{3}v_{1}$ is a proper $C_{6}$.

Thus, we may also assume $v_{4}v_{6}$ is blue.  The cycle $v_{1}v_{4}v_{6}v_{7}v_{2}v_{3}v_{1}$ shows that $v_{2}v_{7}$ must be green which immediately implies $v_{7}v_{4}$ is blue since $v_{7}$ needs a blue edge.  The cycle $v_{1}v_{4}v_{7}v_{5}v_{2}v_{3}v_{1}$ implies $v_{5}v_{2}$ must be green while the cycle $v_{1}v_{4}v_{7}v_{6}v_{2}v_{3}v_{1}$ implies $v_{6}v_{2}$ is also green.  Since $v_{2}$ needs a blue edge, $v_{4}v_{2}$ must be blue.  Then $v_{1}v_{4}v_{2}v_{5}v_{3}v_{7}v_{1}$ is a proper $C_{6}$ to complete the proof in this case.

\begin{case}
$n=6$.
\end{case}

As in the previous cases, there must be three colors that are \gn{spanning and} connected. By Theorem~\ref{diam2}, the diameter of each color can be at most four.   Recall that in the base case of Theorem~\ref{C5Thm}, we argue that each $G^i$ has exactly five edges and that if each $G^i$ has a diameter of at most three, then each $G^i$ is a $T_{1}$.  Thus, if no color has diameter four, \gn{then up to relabeling} of colors, there is exactly one coloring of $G$ in which each color induces a $T_{1}$.  This coloring is shown in Figure~\ref{Figure:K6} below.


\begin{figure}[ht!]
\begin{center}
% \epsfxsize = 2in
% \epsfbox{K6-3Colors.2}
 \epsfbox{K6-3Colors.1}
%%%%%%% \epsfbox{K6_3ConnColors_Diam3.eps}
 \caption{Coloring of $K_{6}$ \label{Figure:K6}}
\end{center}
\end{figure}

In Figure~\ref{Figure:K6}, we see that $v_5v_6v_4v_2v_3v_1v_5$ is a proper $C_6$.   We now assume that there is a color, say color 1, with diameter exactly four.  For the duration of the proof, we rely on the following claim.

\begin{claim}\label{K6TriangleClaim}
In any coloring $G$ of $K_6$ with three spanning and connected colors, $G$ does not contain a monochromatic triangle.
\end{claim}

\begin{proof}
This proof is by contradiction.  Assume $G$ has a monochromatic triangle in color $i$.  \gn{Since $G$ has three spanning and connected colors,} $G^i$ has exactly five edges.  Since $G^i$ contains a triangle $v_1v_2v_3$, $G^i$ has exactly two other edges that must connect the remaining three vertices $v_4v_5v_6$ to the triangle, a contradiction.
\end{proof}

Since color $1$ has diameter exactly four, $G^1$ has a path $v_1v_2v_3v_4v_5$ with no chords of color $1$.  If edge $v_3v_6$ is color $1$, then $G^1$ has three disjoint color $1$ edges and we can easily find a $C_6$ in $G$.  Since $G^1$ is spanning, this forces that either edge $v_2v_6$ or $v_4v_6$ is color $1$.  Without loss of generality, assume $v_2v_6$ is color $1$. We also know that edges $v_1v_6$ and $v_5v_6$ are not color $1$ because otherwise the diameter of $G^1$ is not four.  We now consider two subcases.

\begin{subcase}
$v_1v_6$ and $v_5v_6$ have the same color.
\end{subcase}

Assume $v_1v_6$ and $v_5v_6$ have color $2$. Then $v_1v_5$ must be color $3$ or triangle $v_1v_5v_6$ forms a monochromatic triangle, thus contradicting Claim~\ref{K6TriangleClaim}.  If $v_3v_5$ is color $2$, then $v_1v_6v_2v_4v_3v_5v_1$ is a proper $C_6$, so assume $v_3v_5$ is instead color $3$.  If $v_1v_3$ is color $3$, then triangle $v_1v_3v_5$ is a monochromatic triangle, again contradicting Claim~\ref{K6TriangleClaim}. Thus, $v_1v_3$ is color $2$.  Finally, this implies that $v_3v_6$ must be color 3 or otherwise $v_1v_3v_6$ is a monochromatic triangle in color $2$, another contradiction of Claim~\ref{K6TriangleClaim}.  In this structure, we see that $v_1v_2v_4v_5v_6v_3v_1$ is a proper $C_6$.

\begin{subcase}
$v_1v_6$ and $v_5v_6$ have different colors.
\end{subcase}

If edge $v_1v_3$ also has a different color from edge $v_1v_6$, then $v_1v_6v_5v_4v_2v_3v_1$ is a proper $C_6$.  Thus, $v_1v_3$ and $v_1v_6$ have the same color and \gn{similarly} $v_3v_5$ and $v_5v_6$ have the same color.  This forces either $v_1v_3v_6$ or $v_3v_5v_6$ to be a monochromatic triangle, which contradicts Claim~\ref{K6TriangleClaim}.
\end{proof}


% ---------------------
\section{Proper-$C_{m}$ free Colorings} \label{Section:General}
% ---------------------
The results contained in the previous sections establish that two or more spanning and connected colors imply the existence of a proper $C_4$, while three or more spanning and connected colors imply the existence of a proper $C_5$ and a proper $C_6$.  The next result shows that as the desired cycle length gets longer, we need more and more spanning and connected colors to force the existence of a properly colored cycle.  Specifically, Theorem~\ref{2colorscon} ensures that we need at least $k+1$ spanning and connected colors to force the existence of a proper $C_m$, for $m > 2k$.

\begin{theorem}\label{2colorscon}
For $n \geq 2k$, there exists a coloring of $K_{n}$ which contains $k$ spanning and connected colors but no proper cycles of length greater than $2k$.
\end{theorem}

\begin{proof}
The construction is by induction on $n$.  Suppose there exists a coloring $G$ of $K_{n - 2k}$ which contains no proper cycle of length greater than $2k$.  If $n \leq 4k$, this is trivial so we may suppose $n > 4k$.  Add $2k$ new vertices $\{u_{1}, \dots, u_{k}, v_{1}, \dots, v_{k}\}$ to $G$.  For all $i \geq j$, color the edges $u_{i}v_{j}$ and $v_{i}u_{j}$ with color $j$.  For $i < j$, color the edges $u_{i}u_{j}$ and $v_{i}v_{j}$ with color $j$.  This provides a coloring of all the edges among pairs of the added vertices.  All edges between $u_{i}$ and $G$ and between $v_{i}$ and $G$ receive color $i$.  In this coloring of $K_{n}$, colors $1, 2, \dots, k$ are \gn{spanning and} connected.

Suppose there exists a properly colored cycle $C = C_{m}$ in this graph for some $m > 2k$.  Since $G$ was assumed to have no properly colored $C_{m}$, we know $C \nsubseteq G$.  Conversely, since $|C| = m > 2k$, we also know that $C \nsubseteq \{u_{1}, \dots, u_{k}, v_{1}, \dots, v_{k}\}$.  Consider an edge $e$ of $C$ from $G$ to $u_{i}$ (or identically $v_{i}$).  By construction, $e$ has color $i$.  Following $C$ from $u_{i}$, \gn{we cannot take an edge of color $i$, so must take an edge of color $j$ to a vertex $u_{j}$ for $j \geq i$ or $v_{j}$ for $j < i$.  Similar statements hold when leaving $u_{j}$ or $v_{j}$, and we see that we can never return to $G$.  This is a contradiction.}  Note that all colors are \gn{spanning and} connected.  \end{proof}

Theorem~\ref{2colorscon} yields a lower bound for the number of spanning and connected colors required to force the existence of a properly colored cycle.
Theorem~\ref{GenCycles} yields a general upper bound and shows that any coloring with $2m-1$ or more \gn{spanning and} connected colors forces the existence of a proper $C_m$, for $m\geq 3$.

\begin{theorem}\label{GenCycles}
Let $m \geq 3$ and $n \geq m$.  If $G$ is a proper-$C_m$ free coloring of $K_n$, then $G$ has at most $2m - 2$ spanning and connected colors.
\end{theorem}

\begin{proof}
This proof is by induction on $m$.  If $m \leq \gn{6}$, the result follows from Theorems~\ref{gallai},~\ref{C4Discon},~\ref{C5Thm}, \gn{and~\ref{C6Thm}} so suppose $m \geq \gn{7}$.  Let $G$ be a coloring of $K_{n}$ with at least $2m - 1$ colors spanning connected graphs and suppose $G$ contains no proper $C_{m}$.  Note that this implies $n \geq 2m$.  By induction, we may assume there is a properly colored $C_{m - 1}$ in $G$.  Call this cycle $C$.  We now prove a sequence of claims which lead to the construction of a proper $C_{m}$.

\begin{claim}\label{NewColors}
If $w \in G \setminus C$ has an edge $e$ to $C$ of color $i$ where $i$ is not used in $C$, then $w$ has only edges \gn{in} color $i$ to $C$.
\end{claim}

\begin{proof}
Let $c_{1}$ be the vertex of $C$ contained in $e$ and let $c_{2}, c_{3}, \dots, c_{m - 1}$ be the remaining vertices of $C$ in order around $C$.  Let $i_{1}, i_{2}, \dots, i_{m - 1}$ be the colors of the edges \gn{in} $C$ such that the color of $c_{j}c_{j + 1}$ is $i_{j}$ (where the indices are taken modulo $m - 1$).  In order to avoid creating a properly colored $C_{m}$, the edge $wc_{2}$ must either have color $i$ or $i_{2}$.  Let $j_{2} \in \{i, i_{2}\}$ be the color of $wc_{2}$.  Similarly, the edge $wc_{3}$ must either have color $j_{2}$ or $i_{3}$.  Let $j_{3} \in \{j_{2}, i_{3}\}$ be the color of $wc_{3}$.  Following this pattern, let $j_{t}$ denote the color of the edge $wc_{t}$ where $j_{t} \in \{ j_{t - 1}, i_{t}\}$ for all $2 \leq t \leq m - 1$.  Since the edge $wc_{1}$ has color $i$, it must be that $i$ is in the set $\{j_{m - 1}, i_{1}\}$.  Since $i$ is unused in $C$, we must have $j_{m - 1} = i$.  This, in turn, implies that $i \in \{j_{m - 2}, i_{m - 1}\}$, so again $j_{m - 2} = i$.  This argument can be repeated all the way around $C$ to conclude that the color of $wc_{j}$ is $i$ for all $j$.  \end{proof}

Without loss of generality, suppose $C$ uses colors $m + 1, m + 2, \dots, m + s$ where $s \leq m - 1$.  Since $2m - 1$ colors are \gn{spanning and} connected, we may assume colors $1, 2, \dots, m$ are all \gn{spanning and} connected and not present in $C$.  For all $i \geq 1$, let $V_{i}$ be the set of vertices in $G \setminus C$ with all edges to $C$ in color $i$.  Since colors $1, 2, \dots, m$ are all \gn{spanning and} connected, applying Claim~\ref{NewColors}, we see that $V_{i} \neq \emptyset$ for all $i \leq m$.

\begin{claim}\label{AllIn}
\gn{If $w \in G \setminus (\cup_{i \geq 1} V_{i})$ and $v \in V_{i}$, then $wv$ has color $i$.}
%If we let $H = G \setminus (\cup_{i \geq 1} V_{i})$, then there exists no edge from $v \in V_{i}$ for $1 \leq i \leq m$ to $w \in H$ in color $j \neq i$.
\end{claim}

\begin{proof}
This proof is by contradiction.  By the definition of $V_{i}$, all edges between $V_{i}$ and $C$ have color $i$ so if $H = C$, we're finished.  Thus, we may assume $H \setminus C \neq \emptyset$.  Let $w \in H \setminus C$ and suppose $v \in V_{i}$ and $vw$ has color $j \neq i$ where $j$ is not used in $C$.  Since $w \notin \cup V_{i}$, there exists an edge $wc_{1}$ with color $k \neq j$ for some $c_{1} \in C$.  Again let $c_{i}$ denote the vertices of $C$ in order around the cycle.  Since either $c_{m - 1}c_{1}$ or $c_{1}c_{2}$ has a color other than $k$, we will assume the color of $c_{m - 1}c_{1}$ is $\ell \neq k$ (see Figure~\ref{EdgesOut}).  Now, by considering the cycle $wc_{1}c_{m - 1} \cdots c_{3}vw$, we see that the color of $c_{3}c_{4}$ must be $i$ since otherwise this produces a proper $C_{m}$, a contradiction.  \end{proof}

\begin{figure}[ht!]
\begin{center}
 \epsfxsize 2in \epsfbox{EdgesOut.1}
 \caption{Structure of $G$ \label{EdgesOut}}
\end{center}
\end{figure}

%Now consider the edge $wc_{2}$.  If this edge has color $j$, then to avoid a proper $C_{m}$, the edge $c_{2}c_{3}$ must also have color $j$, meaning that $j$ is used in $C$, a contradiction.  This means that $wc_{2}$ must not have color $j$, and must have either color $k$ or the color of $c_{2}c_{3}$.  In the latter case, the cycle $wc_{2}c_{1}c_{m - 1} \cdots c_{4}vw$ is a proper $C_{m}$ (since the color of $c_{4}c_{5}$ cannot be $i$) so $wc_{2}$ must have color $k$.  To avoid exactly the same proper $C_{m}$, the color of $c_{1}c_{2}$ must be $k$.

Continuing with the proof of Theorem~\ref{GenCycles}, consider edges between sets $V_{i}$ and $V_{j}$ for $1 \leq i, j \leq m$.  Suppose $v_{i} \in V_{i}$ and $v_{j} \in V_{j}$ and the color of $v_{i}v_{j}$ is $k \notin \{i, j\}$.  Then $v_{i}c_{1}c_{2} \cdots c_{m - 2}v_{j}v_{i}$ is the desired proper $C_{m}$.  Note that this holds even if $i = j$.  The next fact is immediate.

\begin{fact}\label{Dependence}
Let $v_{i} \in V_{i}$ and $v_{j} \in V_{j}$ for some $1 \leq i, j \leq m$.  Then the color of $v_{i}v_{j}$ is either $i$ or $j$.
\end{fact}

Note that if $i = j$, this means that the color of $v_{i}v_{j}$ is $i$.

Suppose $1 \leq i, j \leq m$ with $i \neq j$.  By Fact~\ref{Dependence} and Claim~\ref{AllIn}, in order for a vertex in $V_{i}$ to have an edge of color $j$, it must have an edge in color $j$ to a vertex of $V_{j}$.  Since each of these colors is \gn{spanning and} connected, we get the following easy fact.

\begin{fact}\label{FinalFact}
Every vertex in $V_{i}$ must have an edge of color $j$ to a vertex of $V_{j}$ for all $i$ and $j$ with $1 \leq i, j \leq m$.
\end{fact}

Let $v_{1, 1} \in V_{1}$.  By Fact~\ref{FinalFact}, there exists a vertex $v_{2, 1} \in V_{2}$ such that the color of the edge $v_{1, 1}v_{2, 1}$ is $2$.  Similarly, there exists a vertex $v_{3, 1} \in V_{3}$ such that the color of the edge $v_{2, 1}v_{3, 1}$ is $3$.  This process can be continued to create vertices $v_{i, 1}$ for all $1 \leq i \leq m$.  Then there exists a vertex $v_{1, 2} \in V_{1}$ such that $v_{m, 1}v_{1, 2}$ has color $1$.  Note that $v_{1, 2} \neq v_{1, 1}$ since otherwise we would have created a proper (in fact rainbow) $C_{m}$.  Thus, we may continue to create a long proper path using vertices $v_{i, j} \in V_{i}$ where $j$ denotes the number of times we pass through set $V_{i}$.  Since $G$ is finite, this path must repeat a vertex at some point, creating a proper cycle of order a multiple of $m$.  Let $C'$ be the shortest such cycle created by this process which has order a multiple of $m$.  Without loss of generality, suppose $C' = v_{1, 1}v_{2, 1} \cdots v_{m, r}v_{1, 1}$.

Now for all $i$, let $W_{i} \subseteq V_{i}$ denote the vertices of $V_{i}$ which are \gn{also} in $C'$.  Without loss of generality, consider consecutive sets $W_{1}$ and $W_{2}$.  The edges $v_{1, k}v_{2, k}$ must all have color $2$ by construction but all other edges between $W_{1}$ and $W_{2}$ must have color $1$ since otherwise we could create a shorter proper cycle which still has length a multiple of $m$, contradicting the choice of $C'$ (see Figure~\ref{CprimeFig}).  Using the edges between $W_{i}$ and $W_{i + 1}$ which are not in $C'$, we may easily construct a proper $C_{m}$ unless $r = 2$.  In this case, the cycle must look like $v_{1, 1}v_{2, 2}v_{3, 1}v_{4, 2}\cdots v_{m, 1}v_{1, 1}$ but this works only when $m$ is odd.
Thus, we may assume $r = 2$ and $m$ is even.  Consider the edge $v_{1, 1}v_{4, 1}$.  If this edge has color $4$, then $C^{\pp} = v_{1, 1}v_{4, 1}v_{3, 2}v_{4, 2}\cdots v_{m, 2}v_{1, 1}$ is a proper $C_{m}$.  By this argument, all edges of the form $v_{i, 1}v_{i + 3, 1}$ and $v_{i, 2}v_{i + 3, 2}$ have color $i$.  Then we can create all even cycles with length $2t$ a multiple of four from length eight up to $2m$ as follows.  The cycle
$$
v_{1, 1}v_{2, 1} \cdots v_{t, 1}v_{t - 1, 2}v_{t, 2}v_{t - 3, 2}v_{t - 2, 2}v_{t - 5, 2}v_{t - 4, 2} \cdots v_{1, 2}v_{2, 2}v_{1, 1}
$$
is properly colored and has length $2t$.

\begin{figure}[ht!]
\begin{center}
 \epsfxsize 2in \epsfbox{CprimeFig.1}
 \caption{Structure of $C'$ \label{CprimeFig}}
\end{center}
\end{figure}


Finally, \gn{it} remains to produce a proper $C_{2t}$ when $t$ is odd.  If $v_{1, 1}v_{3, 1}$ has color $3$ and $v_{3, 1}v_{5, 1}$ has color $5$, then
$$
v_{1, 1}v_{3, 1}v_{5, 1}v_{6, 1} \cdots v_{t + 1, 1}v_{t, 2}v_{t + 1, 2}v_{t - 2, 2}v_{t - 1, 2}v_{t - 4, 2}v_{t - 3, 2} \cdots v_{1, 2}v_{2, 2}v_{1, 1}
$$
is a properly colored $C_{2t}$ for $t \geq 5$ while $v_{1, 1}v_{3, 1}v_{5, 1}v_{4, 2}v_{1, 2}v_{2, 2}v_{1, 1}$ suffices when $t = 3$.  By symmetry, we cannot have both $v_{1, 1}v_{3, 1}$ in color $1$ and $v_{3, 1}v_{5, 1}$ in color $3$ (by considering the relabeling $v_{1, 1}' = v_{7, 1}$, $v_{2, 1}' = v_{6, 2}$, $v_{3, 1}' = v_{5, 1}$, $v_{4, 1}' = v_{4, 2}$, $\ldots$, $v_{7, 1}' = v_{1, 1}$, $v_{8, 1}' = v_{m, 1}$, $v_{9, 1}' = v_{m - 1, 2}$, $\ldots$ and so on).  By the same argument, we cannot have both $v_{i, j}v_{i + 2, j}$ in color $i$ (or $i + 2$) and $v_{i + 2, j}v_{i + 4, j}$ in color $i + 2$ (or respectively, $i + 4$).  Thus, if $m \geq 8$, we get, either $v_{1, 1}v_{3, 1}$ in color $3$ and $v_{5, 1}v_{7, 1}$ in color $7$ or $v_{1, 1}v_{3, 1}$ in color $1$ and $v_{5, 1}v_{7, 1}$ in color $5$.  In the first case, the desired proper $C_{m}$ is
$$
v_{1, 1}v_{3, 1}v_{4, 1}v_{5, 1}v_{7, 1}v_{8, 1}\cdots v_{m/2 + 1, 1}v_{m/2, 2}v_{m/2 + 1, 2}v_{m/2 - 2, 2}v_{m/2 - 1, 2}v_{m/2 - 4, 2} \cdots v_{1, 2}v_{2, 2}v_{1, 1}
$$
while, in the second case, we use
$$
v_{1, 1}'v_{3, 1}'v_{4, 1}'v_{5, 1}'v_{7, 1}'v_{8, 1}'\cdots v_{m/2 + 1, 1}'v_{m/2, 2}'v_{m/2 + 1, 2}'v_{m/2 - 2, 2}'v_{m/2 - 1, 2}'v_{m/2 - 4, 2}' \cdots v_{1, 2}'v_{2, 2}'v_{1, 1}'.
$$
%For the case when $m = 6$, we get either the cycle $v_{1, 1}v_{3, 1}v_{4, 1}v_{5, 1}v_{1, 2}v_{2, 2}v_{1, 1}$ or the cycle $v_{1, 1}v_{2, 1}v_{1, 2}v_{5, 1}v_{4, 2}v_{3, 1}v_{1, 1}$.  
This completes the proof of Theorem~\ref{GenCycles}.  \end{proof}


We end this section with a corollary summarizing the lower and upper bounds given by Theorems~\ref{2colorscon}~and~\ref{GenCycles}.

\begin{corollary}\label{UpLowBound}
Given integers $m$ and $n$ with $n \geq m$, let $M(m, \gn{n})$ be the maximum number of spanning and connected colors in a coloring of $K_{n}$ containing no proper $C_{m}$.  Then $\frac{m - 1}{2} \leq M(m, \gn{n}) \leq 2m - 2$.
%Assume that the following implication holds: ``If $G$ is a proper $C_{m}$-free coloring of $K_{n}$ for $n\geq m>2k$, then $G$ has at most $M$ spanning and connected colors.''  Then $k\leq M \leq 2m-2$.
\end{corollary}


% ---------------------
\section{Conclusion}
% ---------------------

Future work in the area of proper-cycle free colorings includes tightening the gap between the upper and lower bounds given in Corollary~\ref{UpLowBound}.  The results of Theorems~\ref{C4Discon},~\ref{C5Thm}, and~\ref{C6Thm} indicate that the lower bound of Corollary~\ref{UpLowBound} may be sharp, but in general, this may be difficult to show.  The proofs of Theorems~\ref{C4Discon},~\ref{C5Thm}, and~\ref{C6Thm} do not suggest a way to easily extend the results of proper-$C_4$ free, $C_5$ free, and $C_6$ free colorings to general $C_m$ free colorings.  Since we believe the lower bound in Corollary~\ref{UpLowBound} is sharp (see Conjecture~\ref{LowBoundSharp}), this indicates that the sharp results for even cycles $C_{m}$ may be more difficult to prove since the cycle is longer than the corresponding odd cycle $C_{m - 1}$.  Even so, we conjecture the result is the same.

\begin{conjecture}\label{LowBoundSharp}
Given integers $m$ and $n$ with $n \geq m$, the maximum number of spanning and connected colors in a coloring of $K_{n}$ containing no proper $C_{m}$ is $\gn{ \flr{\frac{m - 1}{2}}}$.
\end{conjecture}

Finding analogs to Theorem~\ref{GallaiDecomp} would also be a welcome addition to the literature; in particular, proving partition results as described in Problem~\ref{PartsProb} for proper-$C_{m}$ free colorings of complete graphs.  We pose the following problem.  %Such a result would open the door for a variety of other structural results within proper-$C_{m}$ free colorings.

\begin{problem}\label{PartsProb}
Given an integer $m$, find the smallest number $\lambda(m)$ such that every proper-$C_{m}$ free coloring of a complete graph has a non-trivial partition with at most $\lambda(m)$ colors on the edges between the parts.
\end{problem}

Some other related results concerning colorings free of proper cycles bear mentioning.  Many such results are contained in \cite{BG09}.  In particular, the following important structural result of Yeo \cite{Y97}.

\begin{theorem}[Yeo \cite{Y97}]\label{yeo}
If $G$ is a proper cycle free coloring of a \emph{(}not necessarily complete\emph{)} graph, then there is a vertex $z \in G$ such that no connected component of $G \setminus \{ z\}$ is joined to $z$ by more than one color.
\end{theorem}

Note that if $G$ is a coloring of $K_n$, Theorem~\ref{yeo} yields the following corollary almost immediately.

\begin{corollary}
If $G$ is a rainbow triangle free and proper-$C_{4}$ free coloring of $K_n$, then there is a vertex $z \in G$ incident only to edges of a single color.
\end{corollary}

Therefore, to gain more structural information about proper-$C_{4}$ free colorings, one may assume the existence of a rainbow triangle.


%With such a result, it would become possible to consider a Ramsey-type problem within the restriction of proper $C_{n}$-free colorings.  More specifically, define the \emph{proper-Ramsey} number $pr_{k}(G : H)$ to be the minimum integer $n$ such that any coloring of the edges of $K_{n}$ with no properly colored $G$ contains a monochromatic copy of $H$.



%\bibliography{ref}
%\bibliographystyle{plain}

\begin{thebibliography}{1}

\bibitem{BG09}
J.~Bang-Jensen and G.~Gutin.
\newblock {\em Digraphs}.
\newblock Springer Monographs in Mathematics. Springer-Verlag London Ltd.,
  London, second edition, 2009.
\newblock Theory, algorithms and applications.

\bibitem{FGMS11}
S.~Fujita, A.~Gy{\'a}rf{\'a}s, C.~Magnant, and A.~Seress.
\newblock Disconnected colors in generalized {G}allai colorings.
\newblock {\em J. Graph Theory}, To appear.

\bibitem{FM11}
S.~Fujita and C.~Magnant.
\newblock Extensions of {G}allai-{R}amsey results.
\newblock {\em J. Graph Theory}, 70(4):404--426, 2012.

\bibitem{FMO10}
S.~Fujita, C.~Magnant, and K.~Ozeki.
\newblock Rainbow generalizations of {R}amsey theory: a survey.
\newblock {\em Graphs and Combin.}, 1:1--30, 2010.

\bibitem{Survey}
S.~Fujita, C.~Magnant, and K.~Ozeki.
\newblock Rainbow generalizations of {R}amsey theory: a survey (upated).
\newblock {\em http://math.georgiasouthern.edu/$\sim$cmagnant/}, 2011.

\bibitem{G67}
T.~Gallai.
\newblock Transitiv orientierbare {G}raphen.
\newblock {\em Acta Math. Acad. Sci. Hungar}, 18:25--66, 1967.

\bibitem{GS04}
A.~Gy{\'a}rf{\'a}s and G.~Simonyi.
\newblock Edge colorings of complete graphs without tricolored triangles.
\newblock {\em J. Graph Theory}, 46(3):211--216, 2004.

\bibitem{Y97}
A.~Yeo.
\newblock A note on alternating cycles in edge-coloured graphs.
\newblock {\em J. Combin. Theory Ser. B}, 69(2):222--225, 1997.

\end{thebibliography}





\end{document}
