Skip to main content
Article
Highly Connected Multicoloured Subgraphs of Multicoloured Graphs
Publications & Research (2008)
  • H. Liu
  • R. Morris
  • N. Prince
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.

Keywords
  • Bollobás,
  • graphs,
  • subgraphs
Publication Date
January 1, 2008
Publisher Statement

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.