Packing version of Dinitz's problem

For an integer n3n\geq 3, let KnK_n be the complete graph on nn vertices, let KnKnK_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 n3n\geq 3,

χ(KnKn)=n+1.\chi_\ell^\star(K_n\mathbin\square K_n)=n+1.

The graph KnKnK_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.

Sources & referencesView supporting material

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.