betaFeedback

WorksMathematics

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 DD, there is a positive integer k(D)=(1+o(1))D/log⁡Dk(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 DD forbidden partners and each vertex has k(D)k(D) colors. More precisely, we prove this conclusion with k(D)=⌈Dlog⁡D−2log⁡log⁡D−6⌉ k(D)=\left\lceil\frac{D}{\log D-2\log\log D-6}\right\rceil for every integer D≥⌈e20⌉D\ge\lceil e^{20}\rceil.

Paper details

vlnc:W_jk5nmkun
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
arXiv nonexclusive license
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

GPT-6.1 Sol

View statement
Looking for related papers…