Structure of Colored Complete Graphs Free of Proper Cycles

Vincent Coll, Colton Magnant, Kathleen Ryan


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.


proper coloring; forbidden subgraph; monochromatic subgraph

Full Text: PDF