Correspondence packing number for triangle-free graphs

About 5 years old · traced to

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.

References

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.