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

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

中文关键词:  $L$-(2,1)-全可标号  $k$-(2,1)-全可选  平面图

英文关键词:$L$-(2,1)-total labeling  $k$-(2,1)-total choosable  planar graphs

中文摘要:

      设图$G$的一个列表分配为映射$L: V(G)\bigcup E(G)\rightarrow2^{N}$. 如果存在函数$c$使得对任意$x\in V(G)\cup E(G)$有$c(x)\in L(x)$满足当$uv\in 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,x\in 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)\leq\Delta+4$.

英文摘要:

      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$.