Show simple item record

dc.contributor.advisorJohnson, Peter
dc.contributor.authorOwens, Andrew
dc.date.accessioned2019-07-18T13:48:22Z
dc.date.available2019-07-18T13:48:22Z
dc.date.issued2019-07-18
dc.identifier.urihttp://hdl.handle.net/10415/6837
dc.description.abstractIt 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.en_US
dc.subjectMathematics and Statisticsen_US
dc.titleRainbow Cycle Forbidding Edge Coloringsen_US
dc.typePhD Dissertationen_US
dc.embargo.lengthen_US
dc.embargo.statusNOT_EMBARGOEDen_US
dc.creator.orcid0000-0001-5891-6001en_US


Files in this item

Show simple item record