Neighbor sum distinguishing total choosability of planar graphs without 4-cycles

详细信息    查看全文

• 作者：Jihui Wang^a ; Jiansheng Cai^b ; Qiaoling Ma^a ; ^{ss_maql@ujn.edu.cn" class="auth_mail" title="E-mail the corresponding author}
• 关键词：Neighbor sum distinguishing total coloring ; Choosability ; Combinatorial Nullstellensatz ; Planar graph
• 刊名：Discrete Applied Mathematics
• 出版年：2016
• 出版时间：19 June 2016
• 年：2016
• 卷：206
• 期：Complete
• 页码：215-219
• 全文大小：360 K

文摘

Let G=(V,E)$G=(V,E)$ be a graph and ϕ$\varphi$ be a total k$k$-coloring of G$G$ by using the color set {1,…,k}$\{1,\dots ,k\}$. Let ∑_ϕ(u)${\sum }_{\varphi }\left(u\right)$ denote the sum of the color of the vertex u$u$ and the colors of all incident edges of u$u$. A k$k$-neighbor sum distinguishing total coloring of G$G$ is a total k$k$-coloring of G$G$ such that for each edge uv∈E(G)$uv\in E\left(G\right)$, ∑_ϕ(u)≠∑_ϕ(v)${\sum }_{\varphi }\left(u\right)\ne {\sum }_{\varphi }\left(v\right)$. By ${\chi }_{\Sigma }^{″}\left(G\right)$, we denote the smallest value k$k$ in such a coloring of G$G$. Pilśniak and Woźniak first introduced this coloring and conjectured that ${\chi }_{\Sigma }^{″}\left(G\right)\le \Delta \left(G\right)+3$ for any simple graph G$G$. Let L_z(z∈V∪E)$L_z(z\in V\cup E)$ be a set of lists of integer numbers, each of size k$k$. The smallest k$k$ for which for any specified collection of such lists, there exists a neighbor sum distinguishing total coloring using colors from L_z$L_z$ for each z∈V∪E$z\in V\cup E$ is called the neighbor sum distinguishing total choosability of G$G$, and denoted by $c{h}_{\Sigma }^{″}\left(G\right)$. In this paper, we prove that $c{h}_{\Sigma }^{″}\left(G\right)\le \Delta \left(G\right)+3$ for planar graphs without 4-cycles with Δ(G)≥7$\Delta \left(G\right)\ge 7$. This implies that Pilśniak and Woźniak’ conjecture is true for planar graphs without 4-cycles.