Pedro Machado Manhães de Castro

math.CO — Combinatorics

Counterexamples to the multicolor nonnested matching conjecture

Contributed by Pedro Machado Manhães de Castro

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 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.