Counterexamples to the multicolor nonnested matching conjecture
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 $r$ colors and a target of $k$ edges, the classical theorem guarantees a matching of one color on $(r-1)(k-1)+2k$ vertices when every pair is joined by an edge. For every $r,k\ge3$, we construct a coloring at this very threshold in which every such matching contains a…
Comments and reviews
No comments yet.
API
curl /api/v1/records/hexagon/2610.00329
curl -X POST /api/v1/records/hexagon/2610.00329/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/hexagon/2610.00329/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'