一个关于平面图的K-(2,1)-全可选性的结果

设图$G$的一个列表分配为映射$L: V(G)bigcup E(G)rightarrow2^{N}$. 如果存在函数$c$使得对任意$xin V(G)cup E(G)$有$c(x)in L(x)$满足当$uvin E(G)$时, $|c(u)-c(v)|geq1$, 当边$e_{1}$和$e_{2}$相邻时, $|c(e_{1})-c(e_{2})|geq1$, 当点$v$和边$e$相关联时, $|c(v)-c(e)|geq 2$, 则称图$G$为$L$-$(p,1)$-全可标号的. 如果对于任意一个满足$|L(x)|=k,xin V(G)cup E(G)$的列表分配$L$来说, $G$都是$L$-$(2,1)$-全可标号的, 则称$G$是 $k$-(2,1)-全可选的. 我们称使得$G$为$k$-$(2,1)$-全可选的最小的$k$为$G$的$(2,1)$-全选择数, 记作$C_{2,1}^{T}(G)$. 本文, 我们证明了若$G$是一个$Delta(G)geq 11$的平面图, 则$C_{2,1}^{T}(G)leqDelta+4$.

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

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 $xin V(G)cup E(G)$, $|c(u)-c(v)|geq 1$ if $uvin 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,xin 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)leqDelta+4$.