Packing version of Dinitz's problem

At least 2 years old · documented by

For an integer n≥3n\geq 3, let KnK_n be the complete graph on nn vertices, let Kn□KnK_n\mathbin\square K_n denote their Cartesian product, and let χℓ⋆\chi_\ell^\star denote the list packing number.

Packing version of Dinitz's problem. For n≥3n\geq 3,

χℓ⋆(Kn□Kn)=n+1.\chi_\ell^\star(K_n\mathbin\square K_n)=n+1.

The graph Kn□KnK_n\mathbin\square K_n is the line graph of Kn,nK_{n,n}, and its ordinary list chromatic number is nn by Galvin's theorem, whereas the paper shows that its list packing number exceeds nn. Determining whether the exact value is n+1n+1 remains open.

References

Primary source

Stijn Cambie, Wouter Cames van Batenburg, Ewan Davies and Ross J. Kang, “List packing number of bounded degree graphs”, arXiv:2303.01246 (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.