Skip to main content
Article
Structure of Colored Complete Graphs Free of Proper Cycles
The Electronic Journal of Combinatorics (2012)
  • Vincent Coll, Lehigh University
  • Colton Magnant, Georgia Southern University
  • Kathleen Ryan, Lehigh University
Abstract

For a fixed integer m, we consider edge colorings of complete graphs which contain no properly edge colored cycle Cm 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 C4, C5, and C6, we show that our bounds are sharp.

Keywords
  • Proper coloring,
  • Forbidden subgraph,
  • Monochromatic subgraph
Disciplines
Publication Date
January 1, 2012
Citation Information
Vincent Coll, Colton Magnant, and Kathleen Ryan. "Structure of Colored Complete Graphs Free of Proper Cycles" The Electronic Journal of Combinatorics 19.4 (2012).
source:http://www.combinatorics.org/ojs/index.php/eljc/article/view/v19i4p33/pdf
Available at: http://works.bepress.com/colton_magnant/29