A Result on $K$-(2,1)-Total Choosability of Planar Graphs

Abstract:

      A list assignment of a graph $G$ is a function $L:V(G)\cup E(G)\rightarrow 2^{N}$. A graph $G$ is $L$-(2,1)-Total labeling if there exists a function $c$ such that $c(x)\in L(x)$ for all $x\in V(G)\cup E(G)$, $|c(u)-c(v)|\geq 1$ if $uv\in E(G)$, $|c(e_{1})-c(e_{2})|\geq 1$ if the edges $e_{1}$ and $e_{2}$ are adjacent, and $|c(u)-c(e)|\geq 2$ if the vertex $u$ is incident to the edge $e$. A graph $G$ is $k$-(2,1)-Total choosable if G is $L$-(2,1)-Total labeling for every list assignment $L$ provided that $|L(x)|=k,x\in V(G)\cup E(G)$. The $(2,1)$-Total choice number of $G$, denoted by $C_{2,1}^{T}(G)$, is the minimum $k$ such that $G$ is $k$-(2,1)-Total choosable. In this paper, we prove that if $G$ is a planar graph with $\Delta(G)\geq 11$, then $C_{2,1}^{T}(G)\leq\Delta+4$.