Total weight choosability for Halin graphs

Abstract

A proper total weighting of a graph $G$ is a mapping $\varphi$ which assigns to each vertex and each edge of $G$ a real number as its weight so that for any edge $uv$ of $G$, ${\sum }_{e\in E(v)}\varphi (e)+\varphi (v)\ne {\sum }_{e\in E(u)}\varphi (e)+\varphi (u)$. A $(k,k^{\prime })$-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^{\prime }$ permissible weights. An $L$-total weighting is a total weighting $\varphi$ with $\varphi (z)\in L(z)$ for each $z\in V(G)\cup E(G)$. A graph $G$ is called $(k,k^{\prime })$-choosable if for every $(k,k^{\prime })$-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.

References in corpus (1)

• The 1-2-3 Conjecture and related problems: a survey