Answers are grounded in this paper and cite their sources.
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)=/log D-2loglog D-6 \] for every integer D≥ e²⁰.
No takes yet. Share an insight, caveat, or question.
Xin Zhang (2026) studied this question.
Synapse has enriched 8 closely related papers on similar clinical questions. Consider them for comparative context: