Total weight choosability of graphs

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 ∪ E and 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 K 2 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