The diagonal-maximality conjecture for correspondence packing of complete bipartite graphs

For positive integers aa and bb with a>ba>b, let Ka,bK_{a,b} denote the complete bipartite graph with parts of sizes aa and bb, and let χc\chi_c^\star denote its correspondence packing number. Diagonal-maximality conjecture.

χc(Ka+1,b)χc(Ka,b+1).\chi_c^\star(K_{a+1,b})\le \chi_c^\star(K_{a,b+1}).

Thus, among complete bipartite graphs with a fixed total number of vertices, the maximum value is conjectured to occur on the diagonal, in the sense stated above. The source notes that this is analogous to a belief about Ramsey numbers and is also expected for the list and correspondence colouring parameters; no resolution is supplied.

Sources & referencesView supporting material

Primary source

Stijn Cambie and Rimma Hämäläinen, “Packing colourings in complete bipartite graphs and the inverse problem for correspondence packing”, arXiv:2303.01944 (2024).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.