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.

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