Generalized Petersen graphs are (1,3)-choosable

Abstract

A total weighting of a graph $G$ is a mapping $\varphi$ that assigns a weight to each vertex and each edge of $G$. The vertex-sum of $v\in V(G)$ with respect to $\varphi$ is $S_{\varphi }(v)={\sum }_{e\in E(v)}\varphi (e)+\varphi (v)$. A total weighting is proper if adjacent vertices have distinct vertex-sums. A graph $G=(V,E)$ is called $(k,k^{\prime })$-choosable if the following is true: If each vertex $x$ is assigned a set $L(x)$ of $k$ real numbers, and each edge $e$ is assigned a set $L(e)$ of $k^{\prime }$ real numbers, then there is a proper total weighting $\varphi$ with $\varphi (y)\in L(y)$ for any $y\in V\cup E$. In this paper, we prove that the generalized Petersen graphs are $(1,3)$-choosable.

11 pages, 5 figures