Skip to main content
Article
Forbidden Rainbow Subgraphs that Force Large Highly Connected Monochromatic Subgraphs
SIAM Journal on Discrete Math
  • Shinya Fujita
  • Colton Magnant, Georgia Southern University
Document Type
Article
Publication Date
1-1-2013
DOI
10.1137/120896906
Disciplines
Abstract
We consider a forbidden rainbow structure condition which implies that an edge colored complete graph has an almost spanning monochromatic subgraph with high connectivity. Namely, we classify the connected graphs $G$ that satisfy the following statement: If $n\,{\gg}\,m\,{\gg}\,k$ are integers, then any rainbow $G$-free coloring of the edges of $K_{n}$ using $m$ colors contains a monochromatic $k$-connected subgraph of order at least $n - f(G, k, m)$, where $f$ does not depend on $n$.
Citation Information
Shinya Fujita and Colton Magnant. "Forbidden Rainbow Subgraphs that Force Large Highly Connected Monochromatic Subgraphs" SIAM Journal on Discrete Math Vol. 27 Iss. 3 (2013) p. 1625 - 1637
Available at: http://works.bepress.com/colton_magnant/40/