Counterexamples to the multicolor nonnested matching conjecture
Version 1 / Oct 18, 2026 / CC BY 4.0
Abstract
We show that excluding nested pairs can increase the number of vertices needed to force a matching of one color, disproving a conjecture of Barát, Gyárfás and Tóth. A matching consists of edges with no shared endpoint. In a fixed vertex order, two edges are nested if both endpoints of one lie between those of the other. For colors and a target of edges, the classical theorem guarantees a matching of one color on vertices when every pair is joined by an edge. For every , we construct a coloring at this very threshold in which every such matching contains a nested pair. Thus the nonnested threshold is larger by at least one vertex. Already with three colors, ten vertices force three disjoint edges of one color, while our coloring makes every such triple contain a nested pair. The self-contained proof combines endpoint counts with two edge recolorings that obstruct the pairings allowed by the vertex order.
Provenance statement
Tools used
- OpenAI
- ChatGPT
- OpenAI
- Codex
- Anthropic
- Claude Fable
- Anthropic
- Claude Opus
References
- J. Barát, A. Freschi and G. Tóth, Matchings avoiding ordered patterns . Preprint, arXiv:2512.15461v2 (2025). https://arxiv.org/abs/2512.15461.arXiv
- J. Barát, A. Gyárfás and G. Tóth, Monochromatic spanning trees and matchings in ordered complete graphs . Journal of Graph Theory 105 (4) (2024), 523--541. https://doi.org/10.1002/jgt.23058.DOI
- P. M. M. de Castro, Minimum blockers and extremal graphs for nonnested matchings . Preprint, arXiv:2609.14484v2 (2026). https://arxiv.org/abs/2609.14484v2.arXiv
- E. J. Cockayne and P. J. Lorimer, The Ramsey number for stripes . Journal of the Australian Mathematical Society (Series A) 19 (2) (1975), 252--256. https://doi.org/10.1017/S1446788700029554.DOI
Version history
- v1 · 8 pagesSubmitted by Pedro Machado Manhães de CastroInitial depositCurrentOct 18, 2026