On total weight choosability of graphs

On total weight choosability of graphs

0.00 Avg rating0 Votes
Article ID: iaor20132799
Volume: 25
Issue: 4
Start Page Number: 766
End Page Number: 783
Publication Date: May 2013
Journal: Journal of Combinatorial Optimization
Authors: ,
Keywords: combinatorial optimization
Abstract:

For a graph G with vertex set V and edge set E, a (k,k′)‐total list assignment L of G assigns to each vertex v a set L(v) of k real numbers as permissible weights, and assigns to each edge e a set L(e) of k′ real numbers as permissible weights. If for any (k,k′)‐total list assignment L of G, there exists a mapping f:VE→ℝ such that f(y)∈L(y) for each yVE, and for any two adjacent vertices u and v, ∑ yN(u) f(uy)+f(u)≠ ∑ xN(v) f(vx)+f(v), then G is (k,k′)‐total weight choosable. It is conjectured by Wong and Zhu that every graph is (2,2)‐total weight choosable, and every graph with no isolated edges is (1,3)‐total weight choosable. In this paper, it is proven that a graph G obtained from any loopless graph H by subdividing each edge with at least one vertex is (1,3)‐total weight choosable and (2,2)‐total weight choosable. It is shown that s‐degenerate graphs (with s≥2) are (1,2s)‐total weight choosable. Hence planar graphs are (1,10)‐total weight choosable, and outerplanar graphs are (1,4)‐total weight choosable. We also give a combinatorial proof that wheels are (2,2)‐total weight choosable, as well as (1,3)‐total weight choosable.

Reviews

Required fields are marked *. Your email address will not be published.