Four-colour counterexamples for monochromatic path partitions
Source: arxiv.org/abs/2611.06362
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\geq118$, we construct a four-edge-colouring of $K_n$ in which every monochromatic path partition contains at least five paths. We also…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2611.06362
curl -X POST /api/v1/records/arxiv/2611.06362/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2611.06362/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'