Bounding the monomial index and (1, l)-weight choosability of a graph

Let G = (V, E) be a graph. For each e is an element of E(G) and nu is an element of V (G), let L-e and L-v, respectively, be a list of real numbers. Let w be a function on V (G) boolean OR E(G) such that w(e) is an element of L-e for each e is an element of E(G) and w(v) is an element of L-v for each v is an element of V (G), and let c(w) be the vertex colouring obtained by c(w) (v) = w(v) + Sigma(e there exists v) w(e). A graph is (k, /)-weight choosable if there exists a weighting function w for which c, is proper whenever |L-v| >= k and |L-e| >= l for every v is an element of V (G) and e is an element of E(G). A sufficient condition for a graph to be (1, /)-weight choosable was developed by Bartnicki, Grytczuk and Niwczyk (2009), based on the Combinatorial Nullstellensatz, a parameter which they call the monomial index of a graph, and matrix permanents. This paper extends their method to establish the first general upper bound on the monomial index of a graph, and thus to obtain an upper bound on 1 for which every admissible graph is (1, l)-weight choosable. Let 02 (G) denote the smallest value 8 such that every induced subgraph of G has vertices at distance 2 whose degrees sum to at most 8. We show that every admissible graph has monomial index at most partial derivative(2) (G) and hence that such graphs are (1, partial derivative(2) (G)+1)-weight choosable. While this does not improve the best known result on (1, 1)-weight choosability, we show that the results can be extended to obtain improved bounds for some graph products; for instance, it is shown that G square K-n is (1, rid 3)-weight choosable if G is d-degenerate.