# zbMATH — the first resource for mathematics

Bounding the monomial index and $$(1,l)$$-weight choosability of a graph. (English) Zbl 1302.05059
Summary: Let $$G = (V,E)$$ be a graph. For each $$e \in E(G)$$ and $$v \in V(G)$$, let $$L_{e}$$ and $$L_{v}$$, respectively, be a list of real numbers. Let $$w$$ be a function on $$V(G) \cup E(G)$$ such that $$w(e) \in L_{e}$$ for each $$e \in E(G)$$ and $$w(v) \in L_{v}$$ for each $$v \in V(G)$$, and let $$c_{w}$$ be the vertex colouring obtained by $$c_{w}(v) = w(v) + \sum _{e \ni v}w(e)$$. A graph is $$(k,l)$$-weight choosable if there exists a weighting function $$w$$ for which $$c_{w}$$ is proper whenever $$|L_{v}| \geq k$$ and $$|L_{e}| \geq l$$ for every $$v \in V(G)$$ and $$e \in E(G)$$. A sufficient condition for a graph to be $$(1,l)$$-weight choosable was developed by T. Bartnicki et al. [J. Graph Theory 60, No. 3, 242–256 (2009; Zbl 1210.05138)], 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 l for which every admissible graph is $$(1,l)$$-weight choosable. Let $$\partial _{2}(G)$$ denote the smallest value $$s$$ such that every induced subgraph of $$G$$ has vertices at distance 2 whose degrees sum to at most $$s$$. We show that every admissible graph has monomial index at most $$\partial _{2}(G)$$ and hence that such graphs are $$(1, \partial _{2}(G)+1)$$-weight choosable. While this does not improve the best known result on $$(1,l)$$-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, nd+3)$$-weight choosable if $$G$$ is $$d$$-degenerate.

##### MSC:
 05C15 Coloring of graphs and hypergraphs 05C78 Graph labelling (graceful graphs, bandwidth, etc.)
Full Text: