Abstract | ||
---|---|---|
For integers n,r,s,k@?N, n=k and r=s, let m(n,r,s,k) be the largest (in order) k-connected component with at most s colours one can find in anyr-colouring of the edges of the complete graph K\"n on n vertices. Bollobas asked for the determination of m(n,r,s,k). Here, bounds are obtained in the cases s=1,2 and k=o(n), which extend results of Liu, Morris and Prince. Our techniques use Szemeredi's Regularity Lemma for many colours. We shall also study a similar question for bipartite graphs. |
Year | DOI | Venue |
---|---|---|
2009 | 10.1016/j.disc.2009.06.022 | Discrete Mathematics |
Keywords | Field | DocType |
graph ramsey numbers,k -connected graphs,regularity lemma,k-connected graphs,connected graph,complete graph,ramsey number,connected component,bipartite graph,k | Integer,Discrete mathematics,Complete graph,Combinatorics,Vertex (geometry),Bipartite graph,Ramsey's theorem,Connectivity,Mathematics,Lemma (mathematics) | Journal |
Volume | Issue | ISSN |
309 | 21 | Discrete Mathematics |
Citations | PageRank | References |
0 | 0.34 | 4 |
Authors | ||
2 |
Name | Order | Citations | PageRank |
---|---|---|---|
Henry Liu | 1 | 16 | 5.35 |
Yury Person | 2 | 118 | 19.19 |