Total weight choosability for Halin graphs

Yu-Chang Liang, Tsai-Lien Wong, Xuding Zhu


A proper total weighting of a graph G is a mapping φ which assigns to each vertex and each edge of G a real number as its weight so that for any edge uv of G, ΣeE(v) φ(e)+φ(v) ≠ ΣeE(u)φ(e)+φ(u). A (k,k')-list assignment of G is a mapping L which assigns to each vertex v a set L(v) of k permissible weights and to each edge e a set L(e) of k' permissible weights. An L-total weighting is a total weighting φ with φ(z) ∈ L(z) for each z ∈ V(G) ∪ E(G). A graph G is called  (k,k')-choosable if for every (k,k')-list assignment L of G, there exists a proper L-total weighting.   As a strenghtening of the well-known 1-2-3 conjecture,  it was conjectured in [Wong and Zhu, Total weight choosability of graphs, J. Graph Theory 66 (2011), 198-212] that every graph without  isolated edge is (1,3)-choosable.  It is easy to verified this conjecture for trees, however, to prove it for wheels seemed to be quite non-trivial.  In this paper, we develop some tools  and techniques  which enable us to prove this conjecture for generalized  Halin graphs.


total weighting; $(k,k')$-matrix; Halin graphs

Full Text:




L. Addario-Berry, R.E.L. Aldred, K. Dalal, and B.A. Reed, Vertex colouring edge partitions, J. Combin. Theory Ser. B, 94 (2005), 237–244.

L. Addario-Berry, K. Dalal, C. McDiarmid, B.A. Reed, and A. Thomason, Vertex-colouring edge-weightings, Combinatorica 27 (2007), 1–12.

N. Alon, Combinatorial Nullstellensatz, Combin. Prob. Comput. 8 (1999), 7–29.

N. Alon and M. Tarsi, A nowhere zero point in linear mappings, Combinatorica 9 (1989), 393–395.

N. Alon and M. Tarsi, Colorings and orientations of graphs, Combinatorica 12 (1992), 125–134.

T. Bartnicki, J. Grytczuk and S. Niwczyk,Weight choosability of graphs, J. Graph Theory 60 (2009), 242–256.

G.J. Chang, C. Lu, J.Wu, and Q.L. Yu, Vertex coloring 2-edge weighting of bipartite graphs, Taiwanese Journal of Mathematics 15 (4) (2011), 1807–1813.

M. Kalkowski, A note on 1, 2-Conjecture, manuscript.

M. Karonski, T. Łuczak, and A. Thomason, Edge weights and vertex colours, J. Combin. Theory Ser. B 91 (2004), 151–157.

M. Kalkowski, M. Karonski, and F. Pfender, Vertex-coloring edge-weightings: towards the 1-2-3- Conjecture, J. Combin. Theory Ser. B 100 (2010), 347–349.

H. Lu, Q. Yu, and C.-Q. Zhang, Vertex-coloring 2-edge-weighting of graphs, European J. Combin. 32 (2011) 21–27.

H. Pan and D. Yang, On total weight choosability of graphs, J. Comb. Optim. 25 (2013), 766–783.

J. Przybyło and M. Wozniak, On a 1-2 conjecture, Discrete Math. Theor. Comput. Sci. 12 (2010), 101–108.

J. Przybyło and M. Wo´zniak, Total weight choosability of graphs, Electron. J. Combin. 18 (2011), no. 1, Paper 112, 11 pp.

U. Schauz, Algebraically solvable problems: describing polynomials as equivalent to explicit solutions, Electron. J. Combin. 15 (2008), no. 1, Research Paper 10, 35 pp.

B. Seamone, The 1-2-3 conjecture and related problems: a survey, submitted (

T. Wang and Q. L. Yu, A note on vertex-coloring 13-edge-weighting, Frontier Math. 4 in China, 3 (2008), 1–7.

T. Wong, D. Yang, and X. Zhu, List total weighting of graphs, Fete of combinatorics and computer science, 337–353, Bolyai Soc.Math. Stud., 20, Janos Bolyai Math. Soc., Budapest, 2010.

T. Wong, J. Wu, and X. Zhu, Total weight choosability of Cartesian product of graphs, European J. Combinatorics 33 (2012), 1725–1738.

T. Wong and X. Zhu, Total weight choosability of graphs, J. Graph Theory 66 (2011), 198–212.

T. Wong and X. Zhu, Permanent index of matrices associated with graphs, Electron. J. Combin. 24 (2017), no. 1, Paper 1.25, 11 pp

T. Wong and X. Zhu, Every graph is (2, 3)-choosable, Combinatorica 36 (2016), 121–127.


  • There are currently no refbacks.

ISSN: 2338-2287

Creative Commons License
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.

View EJGTA Stats