Total weight choosability of d-degenerate graphs

Abstract

A graph $G$ is $(k,k^{\prime })$-choosable if the following holds: For any list assignment $L$ which assigns to each vertex $v$ a set $L(v)$ of $k$ real numbers, and assigns to each edge $e$ a set $L(e)$ of $k^{\prime }$ real numbers, there is a total weighting $\varphi :V(G)\cup E(G)\to R$ such that $\varphi (z)\in L(z)$ for $z\in V\cup E$, and ${\sum }_{e\in E(u)}\varphi (e)+\varphi (u)\ne {\sum }_{e\in E(v)}\varphi (e)+\varphi (v)$ for every edge $uv$. This paper proves the following results: (1) If $G$ is a connected $d$-degenerate graph, and $k>d$ is a prime number, and $G$ is either non-bipartite or has two non-adjacent vertices $u,v$ with $d(u)+d(v)<k$, then $G$ is $(1,k)$-choosable. As a consequence, every planar graph with no isolated edges is $(1,7)$-choosable, and every connected $2$-degenerate non-bipartite graph other than $K_2$ is $(1,3)$-choosable. (2) If $d+1$ is a prime number, $v_1,v_2,\dots ,v_n$ is an ordering of the vertices of $G$ such that each vertex $v_i$ has back degree $d^{-}(v_i)\le d$, then there is a graph $G^{\prime }$ obtained from $G$ by adding at most $d-d^{-}(v_i)$ leaf neighbours to $v_i$ (for each $i$) and $G^{\prime }$ is $(1,2)$-choosable. (3) If $G$ is $d$-degenerate and $d+1$ a prime, then $G$ is $(d,2)$-choosable. In particular, $2$-degenerate graphs are $(2,2)$-choosable. (4) Every graph is $(\lceil \frac{\mathrm{mad}(G)}{2}\rceil +1,2)$ -choosable. In particular, planar graphs are $(4,2)$-choosable, planar bipartite graphs are $(3,2)$-choosable.

16 pages, 1 figures,