Structure of Colored Complete Graphs Free of Proper Cycles

  • Vincent Coll
  • Colton Magnant
  • Kathleen Ryan
Keywords: proper coloring, forbidden subgraph, monochromatic subgraph

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.

Author Biographies

Vincent Coll, Lehigh University
Department of Mathematics
Colton Magnant, Georgia Southern University
Department of Mathematical Sciences
Kathleen Ryan, Lehigh University
Department of Mathematics
Published
2012-12-06
Article Number
P33