Four-colour counterexamples for monochromatic path partitions
Abstract
In 1989, Gyárfás conjectured that the vertex set of every r-edge-coloured complete graph can be partitioned into at most r monochromatic paths. The case r=2 follows from a theorem of Gerencsér and Gyárfás, and Pokrovskiy proved the conjecture for r=3. Recently, Li and Wang disproved the conjecture for all sufficiently large r, leaving open the smallest number of colours for which it fails. We show that this number is four. For every integer n≥118, we construct a four-edge-colouring of Kn in which every monochromatic path partition contains at least five paths. We also construct, for every integer n≥60, a four-edge-colouring of Kn,n in which every monochromatic path partition contains at least eight paths, disproving Pokrovskiy's conjectured bound 2r−1 for balanced complete bipartite graphs when r=4.
Related
- Monochromatic cycle partitions in 3-mean edge-colourings
- Counterexamples and symmetry for uneven orthogonal mass partitions in the plane
- Intersecting integer partitions: star bounds and counterexamples at every scale
- Borsuk-Ulam type theorem for the orthogonal group and orthogonal four-partitions
- Distinct flattened partitions avoiding a pattern of length four
BibTeX
@misc{liu2026fourcolour,
title = {{Four-colour counterexamples for monochromatic path partitions}},
author = {Zhen Liu and Chuanshu Wu},
howpublished = {arXiv},
year = {2026},
month = nov,
doi = {10.48550/arxiv.2611.06362},
eprint = {2611.06362},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2611.06362},
}
RIS
TY - UNPB
TI - Four-colour counterexamples for monochromatic path partitions
AU - Zhen Liu
AU - Chuanshu Wu
PY - 2026
DA - 2026/11/04
PB - arXiv
DO - 10.48550/arxiv.2611.06362
UR - https://arxiv.org/abs/2611.06362
AB - In 1989, Gyárfás conjectured that the vertex set of every r-edge-coloured complete graph can be partitioned into at most r monochromatic paths. The case r=2 follows from a theorem of Gerencsér and Gyárfás, and Pokrovskiy proved the conjecture for r=3. Recently, Li and Wang disproved the conjecture for all sufficiently large r, leaving open the smallest number of colours for which it fails. We show that this number is four. For every integer n≥118, we construct a four-edge-colouring of K_n in which every monochromatic path partition contains at least five paths. We also construct, for every integer n≥60, a four-edge-colouring of K_n,n in which every monochromatic path partition contains at least eight paths, disproving Pokrovskiy's conjectured bound 2r−1 for balanced complete bipartite graphs when r=4.
ER -