Total weight choosability of graphs
Tsai‐Lien Wong, Xuding Zhu · Journal of Graph Theory · 2010
A graph G = (V, E) is called (k, k′)-total weight choosable if the following holds: For any total list assignment L which assigns to each vertex x a set L(x) of k real numbers, and assigns to each edge e a set L(e) of k′ real numbers, there is a mapping f: V∪E→ℝ such that f(y)∈L(y) for any y∈V∪Eand for any two adjacent vertices x, x′, . We conjecture that every graph is (2, 2)-total weight choosable and every graph without isolated edges is (1, 3)-total weight choosable. It follows from results in [7] that complete graphs, complete bipartite graphs, trees other than K2 are (1, 3)-total weight choosable. Also a graph G obtained from an arbitrary graph H by subdividing each edge with at least three vertices is (1, 3)-total weight choosable. This article proves that complete graphs, trees, generalized theta graphs are (2, 2)-total weight choosable. We also prove that for any graph H, a graph G obtained from H by subdividing each edge with at least two vertices is (2, 2)-total weight choosable as well as (1, 3)-total weight choosable. © 2010 Wiley Periodicals, Inc. J Graph Theory 66:198-212, 2011