Structure of Colored Complete Graphs Free of Proper Cycles

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 global structure by bounding the number of colors that can induce a spanning and connected subgraph.  In the case of smaller cycles, namely $C_4,C_5$, and $C_6$, we show that our bounds are sharp.