Name
Abstract | ||
|---|---|---|
Suppose the edges of the complete graph on n vertices, E(K"n), 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 Bollobas, 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>=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, that if r=2s+1 then the answer lies between (1-1/rs)n-7rsk and (1-1/rs)n+1, and that phase transitions occur at [email protected]?r/[email protected]? and [email protected](r). We shall also mention some of the more glaring open problems relating to this question. |
Year | DOI | Venue |
|---|---|---|
2008 | 10.1016/j.disc.2007.09.031 | Discrete Mathematics |
Keywords | Field | DocType |
graph ramsey numbers,k - connected graphs,k-connected graphs,ramsey number,connected graph,graphs,complete graph,k,graph | Graph theory,Discrete mathematics,Complete graph,Graph,Combinatorics,Vertex (geometry),Ramsey's theorem,Connectivity,Mathematics | Journal |
Volume | Issue | ISSN |
308 | 22 | Discrete Mathematics |
Citations | PageRank | References |
4 | 1.07 | 2 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Henry Liu | 1 | 16 | 5.35 |
| Robert Morris | 2 | 4 | 1.07 |
| Noah Prince | 3 | 74 | 9.02 |