Bounding the weight choosability number of a graph

الأصل · EN

Let G = (V,E) be a graph, and for each e ∈ E(G), let Lₑ be a list of real numbers. Let w:E(G) → ∪ₑ ∈ ₑ₍G₎Lₑ be an edge weighting function such that w(e) ∈ Lₑ for each e ∈ E(G), and let cw be the vertex colouring obtained by cw(v) = ∑e vw(e). We desire the smallest possible k such that, for any choice of {Lₑ | e ∈ E(G)} where |Lₑ| ≥ k for all e ∈ E(G), there exists an edge weighting function w for which cw is proper. The smallest such value of k is the weight choosability number of G. This colouring problem, introduced by Bartnicki, Grytczuk and Niwczyk (2009), is the list variation of the now famous 1-2-3 Conjecture due to Karoński, Łuczak, and Thomason (2004). Bartnicki et al. develop a method for approaching the problem based on the Combinatorial Nullstellensatz. Though they show that some particular classes of graphs have weight choosability number at most 3, it was known whether their method could be extended to prove a bound which holds for all admissible graphs. In this paper, we show that this is indeed possible, showing that every graph is (Δ+ d + 1)-weight choosable, where Δ is the graph's maximum degree and d is its degeneracy. In fact, more general results on total weight choosability are provided, where one assigns weights to edges and vertices. Improved bounds are also established for some classes of graph products.