Skip to main content
Article
Forbidden Properly Edge-Colored Subgraphs that Force Large Highly Connected Monochromatic Subgraphs
Graphs and Combinatorics
  • Robert Katic, Georgia Southern University
  • Colton Magnant, Georgia Southern University
  • Pouria Salehi Nowbandegani, Vanderbilt University
Document Type
Article
Publication Date
7-1-2017
DOI
10.1007/s00373-017-1804-5
Disciplines
Abstract

We consider the connected graphs G that satisfy the following property: If nmk are integers, then any coloring of the edges of Kn, using m colors, containing no properly colored copy of G, contains a monochromatic k-connected subgraph of order at least n−f(G,k,m) where f does not depend on n. If we let G denote the set of graphs satisfying this statement, we exhibit some infinite families of graphs in G as well as conjecture that the cycles in G are precisely those whose lengths are divisible by 3. Our main result is that C6G.

Citation Information
Robert Katic, Colton Magnant and Pouria Salehi Nowbandegani. "Forbidden Properly Edge-Colored Subgraphs that Force Large Highly Connected Monochromatic Subgraphs" Graphs and Combinatorics Vol. 33 Iss. 4 (2017) p. 969 - 979 ISSN: 1435-5914
Available at: http://works.bepress.com/colton_magnant/66/