Correspondence packing number for triangle-free graphs

Let GG be a graph and let χc(G)\chi^\star_c(G) denote its correspondence packing number. Let Δ\Delta be a maximum-degree bound.

Triangle-free correspondence packing conjecture.

χc(G)(1+o(1))ΔlogΔ\chi^\star_c(G) \le (1+o(1)) \frac{\Delta}{\log \Delta}

for any triangle-free graph GG with Δ(G)Δ\Delta(G)\le\Delta, as Δ\Delta\to\infty.

The paper proves this asymptotic bound for bipartite graphs, and notes that the complete bipartite examples show the bipartite result is sharp up to an asymptotic factor of 22. Extending it to all triangle-free graphs is left open.

Sources & referencesView supporting material

Primary source

Stijn Cambie, Wouter Cames van Batenburg, Ewan Davies and Ross J. Kang, “Packing list-colourings”, arXiv:2110.05230 (2023).

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.