The power of many colours
A classical problem, due to Gerencsér and Gyárfás from 1967, asks how large a monochromatic connected component can we guarantee in any r-edge colouring of $K_n$ ? We consider how big a connected component we can guarantee in any r-edge colouring of $K_n$ if we allow ourselves to use up...
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Cambridge University Press
2024-01-01
|
| Series: | Forum of Mathematics, Sigma |
| Subjects: | |
| Online Access: | https://www.cambridge.org/core/product/identifier/S2050509424001208/type/journal_article |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Summary: | A classical problem, due to Gerencsér and Gyárfás from 1967, asks how large a monochromatic connected component can we guarantee in any r-edge colouring of
$K_n$
? We consider how big a connected component we can guarantee in any r-edge colouring of
$K_n$
if we allow ourselves to use up to s colours. This is actually an instance of a more general question of Bollobás from about 20 years ago which asks for a k-connected subgraph in the same setting. We complete the picture in terms of the approximate behaviour of the answer by determining it up to a logarithmic term, provided n is large enough. We obtain more precise results for certain regimes which solve a problem of Liu, Morris and Prince from 2007, as well as disprove a conjecture they pose in a strong form. |
|---|---|
| ISSN: | 2050-5094 |