no. 16 · Tuesday 17 November 2026
A proof of a conjecture on bipartite correspondence packing
Abstract
A correspondence cover assigns a set of possible colors to each vertex of a graph. For each edge, a matching between the two endpoint color sets specifies the forbidden color pairs. A correspondence coloring selects one color at each vertex so that no forbidden pair is selected. A full correspondence packing is a collection of such colorings that uses every color at each vertex exactly once. We prove a conjecture of Cambie, Cames van Batenburg, Davies, and Kang [Random Structures & Algorithms 64 (2024), 62–93]. For every sufficiently large $D$, there is a positive integer $k(D)=(1+o(1))D/\log D$ such that every correspondence cover of any finite bipartite graph has a full correspondence packing if each color has at most $D$ forbidden partners and each vertex has $k(D)$ colors. More precisely, we prove this conclusion with \[ k(D)=\left\lceil\frac{D}{\log D-2\log\log D-6}\right\rceil \] for every integer $D\ge\lceil e^{20}\rceil$.
- fields
- Combinatorics