A note about monochromatic components in graphs of large minimum degree
2021
For all positive integers $r\geq 3$ and $n$ such that $r^2-r$ divides $n$ and an affine plane of order $r$ exists, we construct an $r$-edge colored graph with minimum degree $(1-\frac{r-2}{r^2-r})n-2$ such that the largest monochromatic component has order less than $\frac{n}{r-1}$. This generalizes an example of Guggiari and Scott and, independently, Rahimi for $r=3$ and thus disproves a conjecture of Gyarfas and Sarkozy for all integers $r\geq 3$ such that an affine plane of order $r$ exists.
- Correction
- Source
- Cite
- Save
- Machine Reading By IdeaReader
0
References
0
Citations
NaN
KQI