Borowiecki–Jozef Cartesian product list-coloring conjecture

Less than 1 year old · traced to

For graphs G1G_1 and G2G_2, their Cartesian product G1□G2G_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=u′u=u' and vv′∈E(G2)vv'\in E(G_2) or v=v′v=v' and uu′∈E(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

χℓ(G1□G2)≤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.

References

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.