Skip to main content
Article
Highly Connected Monochromatic Subgraphs of Multicoloured Graphs
Faculty Publications & Research
  • H. Liu
  • R. Morris
  • N. Prince, Illinois Mathematics and Science Academy
Document Type
Article
Publication Date
1-1-2009
Disciplines
Abstract

We consider the following question of Bollobás: given an r-coloring of E(Kn), how large a k-connected subgraph can we find using at most s colors? We provide a partial solution to this problem when s=1 (and n is not too small), showing that when r=2 the answer is n−2k+2, when r=3 the answer is ⌊(nk)/2⌋+1 or ⌈(nk)/2⌉+1, and when r−1 is a prime power then the answer lies between n/(r−1)−11(k2−k)r and (nk+1)/(r−1)+r. The case s≥2 is considered in a subsequent paper (Liu et al.[6]), where we also discuss some of the more glaring open problems relating to this question.

Comments

At the time of publication, Noah Prince was affiliated with the University of Illinois at Urbana-Champaign.

Citation Information
Liu, H., Morris, R., Prince, N. (2009). Highly connected monochromatic subgraphs of multicoloured graphs. Journal of Graph Theory, 61(1), 22-44.