Adjacent vertex distinguishing total coloring of planar graphs with maximum degree 8
Adjacent vertex distinguishing total coloring of planar graphs with maximum degree 8
复制标题
最大度数为8的平面图的相邻顶点区分总着色
DOI：
10.1016/j.disc.2020.112014
复制
发表时间：
2020-10
影响因子：
0.8
通讯作者：
Yu Xiaowei
中科院分区：
文献类型：
--
作者：
Chang Yulin;Hu Jie;Wang Guanghui;Yu Xiaowei
摘要 A（本征）全 k 着色 ψ：V (G)∪ E (G)→{1, 2,…, k} 称为相邻顶点，区分每条边 u v∈ E (G) 是否 C ψ (u)≠ C ψ (v)，其中 C ψ (u) 是 u 的颜色和与 u 相关的所有边的颜色的集合。我们用 χ a′′(G) 来表示 G 的这种着色中的最小值 k。Zhang et al.(2005)首先引入了这种着色，并推测对于每个简单图 G，χ a′′(G)≤ Δ (G)+ 3。已知对于每个 Δ (G)≥ 9 的平面图，χ a′′(G)≤ Δ (G)+ 3。在本文中，我们成功了 使用 Alon 的组合 Nullstellensatz 和放电方法证明了每个 Δ (G)≥ 8 的平面图的猜想。
Abstract A (proper) total-k-coloring ϕ: V (G)∪ E (G)→{1, 2,…, k} is called adjacent vertex distinguishing if C ϕ (u)≠ C ϕ (v) for each edge u v∈ E (G), where C ϕ (u) is the set of the color of u and the colors of all edges incident with u. We use χ a′′(G) to denote the smallest value k in such a coloring of G. Zhang et al.(2005) first introduced this coloring and conjectured that χ a′′(G)≤ Δ (G)+ 3 for every simple graph G. It is known that χ a′′(G)≤ Δ (G)+ 3 for every planar graph with Δ (G)≥ 9. In this paper, we succeed in proving the conjecture for every planar graph with Δ (G)≥ 8 by using Alon’s Combinatorial Nullstellensatz and discharging method.
登录
查看更多内容
DOI：
10.1360/012011-359
发表时间：
2012-02
期刊：
--
影响因子：
--
作者：
Danjun Huang;Weifan Wang
通讯作者：
Danjun Huang;Weifan Wang
DOI：
10.1002/(sici)1097-0118(199905)31:1
发表时间：
1999-05
期刊：
J. Graph Theory
影响因子：
--
作者：
C. Bonnington;J. Širáň
通讯作者：
C. Bonnington;J. Širáň
影响因子：
1
作者：
Wang Yiqiao;Wang Weifan
通讯作者：
Wang Weifan
DOI：
10.1057/jors.1977.45
发表时间：
1978-03
期刊：
--
影响因子：
--
作者：
E. Lloyd;J. Bondy;U. Murty
通讯作者：
E. Lloyd;J. Bondy;U. Murty
最大度至少为10的平面图的相邻顶点区分总可选择性
影响因子：
1
作者：
Chang Yulin;Ouyang Qiancheng;Wang Guanghui
通讯作者：
Wang Guanghui