Total weight choosability of Cartesian product of graphs

A graph G=(V,E)G=(V,E) is called (k,k′)(k,k′)-choosable if the following is true: for any total list assignment LL which assigns to each vertex xx a set L(x)L(x) of kk real numbers, and assigns to each edge ee a set L(e)L(e) of k′k′ real numbers, there is a mapping f:V∪E→Rf:V∪E→R such that f(y)∈L(y)f(y)∈L(y) for any y∈V∪Ey∈V∪E and for any two adjacent vertices x,x′x,x′, ∑e∈E(x)f(e)+f(x)≠∑e∈E(x′)f(e)+f(x′)∑e∈E(x)f(e)+f(x)≠∑e∈E(x′)f(e)+f(x′). In this paper, we prove that if GG is the Cartesian product of an even number of even cycles, or the Cartesian product of an odd number of even cycles and at least one of the cycles has length 4n4n for some positive integer nn, then GG is (1,3)(1,3)-choosable. In particular, hypercubes of even dimension are (1,3)(1,3)-choosable. Moreover, we prove that if GG is the Cartesian product of two paths or the Cartesian product of a path and an even cycle, then GG is (1,3)(1,3)-choosable. In particular, Q3Q3 is (1,3)(1,3)-choosable.

► The paper applies combinatorial nullstellensatz to the study of total weight choosability of graphs. ► It gives a sufficient condition in terms of the existence of certain orientations for a graph to be (1, 3)-choosable. ► Hypercubes of even dimension are (1, 3)-choosable.