Highly connected coloured subgraphs via the regularity lemma |
| |
Authors: | Henry Liu Yury Person |
| |
Institution: | aDepartment of Mathematics, University College London, Gower Street, London WC1E 6BT, United Kingdom;bInstitut für Informatik, Humboldt-Universität zu Berlin, Unter den Linden 6, D-10099 Berlin, Germany |
| |
Abstract: | For integers , 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 any r-colouring of the edges of the complete graph Kn on n vertices. Bollobás 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 Szemerédi’s Regularity Lemma for many colours.We shall also study a similar question for bipartite graphs. |
| |
Keywords: | Regularity lemma Graph Ramsey numbers color:black" href="/science?_ob=MathURL&_method=retrieve&_udi=B6V00-4WPS9MX-4&_mathId=mml13&_user=10&_cdi=5632&_rdoc=12&_acct=C000069468&_version=1&_userid=6189383&md5=599cae093b10f4c2798569a9a62cbde4" title="Click to view the MathML source" k-connected graphs" target="_blank">alt="Click to view the MathML source">k-connected graphs |
本文献已被 ScienceDirect 等数据库收录! |
|