Rainbow Cycle Forbidding Edge Colorings

Abstract

It is well known that K_n can be edge colored using n-1 colors in order to avoid rainbow cycles; moreover, this is the maximum number of colors possible. We call such an edge coloring a JL-coloring. In previous work it has been shown that essentially different JL-colorings of K_n are in one-to-one correspondence with (can be encoded by) isomorphism classes of labeled full binary trees on n leafs. Later, this result was shown to be true for complete bipartite graphs as well, with a slight modification to the encoding. In this dissertation, we first show this correspondence extends to all complete multipartite graphs in chapter 2. In chapter 3 we show that if a connected graph G on n vertices is edge colored with n-1 colors and this coloring avoids rainbow cycles, then G has a monochromatic edge cut. It follows that the results from chapter 2 extend to all connected graphs. We also state some results on the sharpness of this result: specifically, what can we say about the number of colors used in an edge coloring that forbids rainbow cycles and monochromatic cuts, and what is the structure of such colorings.

In the last chapter we discuss proper edge colorings which avoid rainbow cycles. In particular, we give several results related to the classification of such edge colorings, including: G ■ H is properly JL-colorable when both G and H are JL-colorable.