Skip to main content
Article
Highly Connected Multicoloured 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-2008
Abstract

Suppose the edges of the complete graph on n vertices, E(Kn), are coloured using r colours; how large a k-connected subgraph are we guaranteed to find, which uses only at most s of the colours? This question is due to Bollobás, and the case s=1 was considered in Liu et al. [Highly connected monochromatic subgraphs of multicoloured graphs, J. Graph Theory, to appear]. Here we shall consider the case s is greater than or equal to 2, proving in particular that when s=2 and r+1 is a power of 2 then the answer lies between 4n/(r+1)-17kr(r+2k+1) and 4n/(r+1)+4 and that phase transitions occur at s=r/2 and when s is of order r^{1/2}. We shall also mention 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. (2008). Highly connected multicoloured subgraphs of multicoloured graphs. Discrete Mathematics, 308(22), 5096-5121.