Borowiecki–Jozef Cartesian product list-coloring conjecture

For graphs G1G_1 and G2G_2, their Cartesian product G1G2G_1\Box G_2 has vertex set V(G1)×V(G2)V(G_1)\times V(G_2), with (u,v)(u,v) adjacent to (u,v)(u',v') when either u=uu=u' and vvE(G2)vv'\in E(G_2) or v=vv=v' and uuE(G1)uu'\in E(G_1). Borowiecki–Jozef's conjecture. For every pair of graphs G1G_1 and G2G_2, there exists a constant CC such that

χ(G1G2)C(χ(G1)+χ(G2)).\chi_\ell(G_1\Box G_2)\leq C\bigl(\chi_\ell(G_1)+\chi_\ell(G_2)\bigr).

The paper presents this as one of two conjectures on Cartesian products and gives no resolution.

Sources & referencesView supporting material

Primary source

Nandana K Vasudevan, K Somasundaram and N Narayanan, “List-Coloring and Chromatic-Choosability – A Dynamic Survey”, arXiv:2606.31702 (2026).

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.