![](https://d3ilqtpdwi981i.cloudfront.net/V9yDQA4pTcSuuGVV7jqYSMNHqmQ=/425x550/smart/https://bepress-attached-resources.s3.amazonaws.com/uploads/bf/68/77/bf68778d-2f8c-4e6d-a1d1-e0c8296a1933/thumbnail_BPFile%20object.jpg)
Article
Highly Connected Multicoloured Subgraphs of Multicoloured Graphs
Publications & Research
(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.
Keywords
- Bollobás,
- graphs,
- subgraphs
Disciplines
Publication Date
January 1, 2008
Citation Information
Liu, H., Morris, R., & Prince, N. (2008). Highly connected multicoloured subgraphs of multicoloured graphs. Discrete Mathematics, 308(22), 5096-5121.
At the time of publication, Noah Prince was affiliated with the University of Illinois at Urbana-Champaign.