Advances in Applied Mathematics 应用数学进展, 2020, 9(8), 1346-1350 Published Online August 2020 in Hans. http://www.hanspub.org/journal/aam https://doi.org/10.12677/aam.2020.98159
Strict Neighbor-Distinguishing Total Coloring of Subcubic Graphs
Hanquan Liu, Jing Gu
College of Mathematics and Computer Science, Zhejiang Normal University, Jinhua Zhejiang
rdthth
Received: Aug. 3, 2020; accepted: Aug. 19, 2020; published: Aug. 26, 2020
Abstract
A proper total k-coloring of a graph G is a mapping ?:V(G)?E(G)→{1,2,?,k}, such that any two adjacent or incident elements in V(G)?E(G) receive different colors. Let Cφ(v) be the set of colors assigned to a vertex v and those edges incident to v. φ is strict neighbor-distinguishing if
C?(u)\\C?(v)≥1 and C?(v)\\C?(u)≥1 for each edge uv∈E(G). The strict neighbor-distin- guishing total index, denoted by χsnt(G), of G is the minimum integer k such that G is k-strict neigh-bor-distinguishing total colorable. In this paper, we prove that every subcubic graph G has χsnt(G)≤6.
Keywords
Strict Neighbor-Distinguishing Total Coloring, Strict Neighbor-Distinguishing Total Index, Subcubic Graphs
子立方图的严格邻点可区别全染色
刘含荃，顾 静
浙江师范大学数学与计算机科学学院，浙江 金华
收稿日期：2020年8月3日；录用日期：2020年8月19日；发布日期：2020年8月26日
摘 要
图G的一个正常k-全染色是指一个映射?:V(G)?E(G)→{1,2,?,k}，使得V(G)?E(G)中任意两个相
文章引用: 刘含荃, 顾静. 子立方图的严格邻点可区别全染色[J]. 应用数学进展, 2020, 9(8): 1346-1350. DOI: 10.12677/aam.2020.98159
刘含荃，顾静
邻的或相关联的元素染不同颜色。令Cφ(v)表示点v的颜色与v的关联边的颜色组成的集合。如果满足对任意一条边uv∈E(G)都有C?(u)\\C?(v)≥1和C?(v)\\C?(u)≥1，则称φ是k-严格邻点可区别的。图G的严格邻点可区别全色数是使G是k-严格邻点可区别全可染的最小正整数k，用χsnt(G)表示。本文证明了每个子立方图满足χsnt(G)≤6。
关键词
严格邻点可区别全染色，严格邻点可区别全色数，子立方图
Copyright ? 2020 by author(s) and Hans Publishers Inc.
This work is licensed under the Creative Commons Attribution International License (CC BY 4.0). http://creativecommons.org/licenses/by/4.0/
Open Access 1. 引言
本文只考虑有限简单图，设G是一个点集为V(G)，边集为E(G)的图，它的最大度，最小度分别为Δ(G)，δ(G)。当点v的度是k时，称为k-点。令NG(v)代表与v相邻的点集。很容易得到对简单图G中的任一点令Pn和Cn分别表示阶为n的路和阶为n的圈。如果图G的每个点的度都是一个固定的常数k，则称G是k-正则的。一个图G如果是3-正则的，则称为立方图；如果满足?(G)≤3，则称为子立方图。图G如果满足δ(G)≥2，则称G为正常的。
关联的元素z1,z2∈V(G)?E(G)，有?(z1)≠?(=z2)。设C?(v)图G的一个正常k-全染色是指一个映射?:V(G)?E(G)→{1,2,?,k}，使得对任意两个相邻的或相v，有dG(v)=NG(v)。在不会混淆的情况下，Δ(G)，δ(G)，dG(v)和NG(v)分别可以写成Δ，δ，d(v)和N(v)。
对相邻的点u和v，有C?(u)≠C?(v)，我们把φ称为邻点可区别的。图G的邻点可区别全色数Xat(G)是使G有一个k-邻点可区别全染色的最小正整数k。此外，如果对任意一对相邻的点u和V，有
{?(v}?{?(e):e∈EG(v)}。如果对任意一
C?(u)\\C?(v)≥1和C?(v)\\C?(u)≥1，我们称φ为严格邻点可区别的。图G的严格邻点可区别全色数
χat(G)是使G有一个k-严格邻点可区别全染色的最小正整数k。
2005年，张忠辅等人在[1]中首先给出了图的邻点可区别全染色的概念，并且对圈、完全图、完全二部图、扇、轮图和树的邻点可区别全染色展开研究，确定了它们的邻点可区别全色数，并根据特殊图的邻点可区别全色数提出了如下猜想：
猜想1 [1]对于阶不少于2的简单连通图G，有χat(G)≤?(G)+3。 如果猜想1成立，则这个上界是紧的。例如，对于任意正整数t≥1，有
Chen和Wang分别在[2]和[3] [4]中证明了?=3的连通图满足猜想1。χat(K2t+1)=2t+1+2=?(K2t+1)+3。
奇数阶的完全图的邻点可区别全色数可以达到猜想1的上界，由于奇数阶的完全图的最大度为偶数，但是对于?=3的连通图，上界6是否是紧的这一问题至今仍未解决。Papaioannou和Raftopoulou在[5]中从算法的角度证明了所有的4-正则图G，有χat(G)≤7，是满足猜想1的。Lu等人在[6]中运用组合零点定理证明了所有?=4的连通图G，有χat(G)≤7，是满足猜想1的。Huang，Wang和Yan在[7]中把?≥3的图的邻点可区别全色数的上界改进到2Δ(G)。
严格邻点可区别全染色(被命名为Smarandachely邻点可区别全染色)有及以下猜想。 猜想2 对于阶不小于2的简单连通图G，有χsnt(G)≤?(G)+3。
2009年，梁少卫在[8]中证明了k≥2的k-正则偶图和k-方体图Qk，满足猜想2。2011年，卫斌等人
DOI: 10.12677/aam.2020.98159
1347
应用数学进展
刘含荃，顾静
在[9]中证明了圈的平方图，满足猜想2。文献[10] [11] [12] [13]中给出了若干类的3-正则图的严格邻点可区别全色数均为5，满足猜想2。2015年，陈妹君等人在[14]中研究了Mycielski图的严格邻点可区别全色数满足猜想2。2019年，李春梅等人在[15]证明了?≤3的2-连通外平面图满足猜想2。
2. 主要结果
在展示主要结果前，我们先建立一些有用的观察。首先，根据定义，以下式子显然成立。 引理1 [2]如果图G是一个?=3的图，则G有一个6-邻点可区别全染色。 引理2 对r≥2，每个r-正则图G满足χsnt(G)=χat(G)。 结合引理1和2，我们得到以下事实：
引理3 如果图G是一个3-正则图，则χsnt(G)≤6。 引理4 对一个阶为n的圈Cn，有χsnt(G)=4。 引理5 对Pn(n≥2)，有χsnt(Pn)=4。
证明：设=Pnv1v2?vn,n≥2，连接v1和vn得到一个圈Cn。设C={1,2,3,4}是一个颜色集合。由引理4，Cn有一个4-严格邻点可区别全染色φ。除了点v1和vn，用与Cn相同的颜色染Pn中的点和边，设
α∈C\\C?(v2)，β∈C\\C?(vn?1)，用α染点v1，用β染点vn。 ?
定理1 如果图G是一个正常的子立方图，则χsnt(G)≤6。
证明：我们用反证法证明。设C={1,2,?,6}是一个颜色集合。假设图G是一个边数E(G)最小的极小反例。如果E(G)≤6，则定理成立，因为足以给每条边分配不同的颜色。所以假设G是一个?≤3，
E(G)≥7的图，且G无法用C中的颜色染好。
如果?=2，G是一个圈或一条路，由引理4和引理5，有χsnt(G)≤6。所以假设?=3。为了完成证明，我们需要构造以下一系列的断言。在断言的证明中，我们用C(v)代替Cφ(v)。
断言1 G不包含1-点。
设N(u)={v,u1,u2}。令H=G?v，则H是一个E(H) 对i∈{1,2}，如果C(ui)\\C(u)=1，取ai∈C(ui)\\C(u)。令α∈C\\C(u)?{a1,a2}，用α染边uv。令β∈C\\C(u)?{α}，用β染点v。断言1的证明完成。 ? 断言2 G不包含相邻2-点。 证明：反之，G包含两个相邻2-点u和v。设N(u)={v,u1}，N(v)={u,v1}。令H=G?uv，则H是一个E(H) 先假设C(u)=C(v)。己知C(v1)?C(v)≤5，令α∈C\\C(v1)?C(v)，用α改染点v。令证明：反之，G包含一个1-点v。设点u是v的邻点。如果d(u)=2，设N(u)={v,u1}；如果d(u)=3， β∈C\\C(u)?{a}，用β染边uv。因此C(u)≠C(v)。如果?(u)=?(v)，令α∈C\\C(v1)?C(v)，用α改染点v。令β∈C\\C(u)?{α,?(vv1)}，用β染边uv。如果?(u)≠?(v)，令β∈C\\C(u)?C(v)，用β 染边uv。断言2的证明完成。 ? 断言3 G中的3-点不与3个2-点相邻。 证明：反之，v是G中的3-点，N(v)={u,x,y}且d=(u)d=(x)d=(y)2。由断言2，u，x，y两两不相邻。令H=G?v，则H是一个E(H) 情形1. C(u)?C(x)?C(y)<6。 DOI: 10.12677/aam.2020.98159 1348 应用数学进展 刘含荃，顾静 令α∈C\\C(u)?C(x)?C(y)，用α染点v。集合C\\{α}中必定存在一个在C(u)，C(x)，C(y)中至多用了一次的颜色，不妨设为1。 因为C(y)?{1,α,β1}≤5，令β2∈C\\C(y)?{1,α,β1}，用β2染边vy。当β1∈C(u)，删去边uv的颜色， 如果1?C(u)?C(x)?C(y)，用1染边uv。令β1∈C\\C(x)?{1,α}，用β1染边vx。当β1?C(u)， 1，取a1∈C′(y)\\C′(v)，因用1染边vy。设C′(v)={1,α,β1}，C′(y)=C(y)?{1}。如果C′(y)\\C′(v)=为C(u)?{1,α,a1}≤5，令β2∈C\\C(u)?{1,α,a1}，用β2染边uv。 如果1∈C(u) (或C(x)，或C(y))，假设C(u)={1,2}。用1染边vx，因为C(y)?{1,2,α}≤5，令 β1∈C\\C(y)?{1,2,α}，用β1染边vy。设C′(v)={1,α,β1}，C′(x)=C(x)?{1}。如果C′(x)\\C′(v)=1， 取a2∈C′(x)\\C′(v)，因为C(u)?{β1,α,a2}≤5，令β2∈C\\C(u)?{β1,α,a2}，用β2染边uv。 情形2. C(u)?C(x)?C(y)=6。 设N(u)={v,u1}，则d(u1)=3。因为C(u1)?C(u)≤5，令α∈C\\C(u1)?C(u)，用α改染点u。此时C(u)?C(x)?C(y)≠C，根据情形1，G有一个6-严格邻点可区别全染色。 断言3的证明完成。 ? 断言4 G中2-点不与3-点相邻。 证明：反之，G包含相邻的3-点u和2-点v，设N(v)={u,w}，因此w是一个3-点。设N(u)={v,u1,u2}，N(w)={v,w1,w2}。u1，u2，w1，w2是2-点或3-点。由断言3，u1或u2是3-点，w1或w2是3-点。不妨设 区别全染色φ，其所用颜色集合为C。如果C(u1)\\C(u)=1，取a∈C(u1)\\C(u)。如果C(w1)\\C(w)=1，取b∈C(w1)\\C(w)。设C(u)={1,2,3}。 情形1. C(u)?C(w)=3。 设α1∈C\\{1,2,3,a}，用α1染边uv。设α2∈C\\{1,2,3,α1,b}，用α2染边vw。设α3∈C\\{α1,α2,?(u),?(w)}，用α3染点v。 情形2. C(u)?C(w)=2。 果α2=3，令α3∈C\\{1,2,3,α1,?(w)}，用α3染点v。如果α2≠3，令α3∈C\\{α1,α2,?(u),?(w)}，用α3染点v。 情形3. C(u)?C(w)=1。 不妨设C(w)={1,4,5}。令α1∈{4,5}\\{a}， α2∈{2,3}\\{b}，用α1染边uv，α2染边vw，6染点v。 情形4. C(u)?C(w)=0。 当?(w1)∈C(w)时，取b′∈C(w1)\\C(w)。令α1∈C\\{4,5,6,b′,?(w2)}，用α1染点w。显然，α1∈{1,2,3}。 不妨设C(w)={4,5,6}，删去点w的颜色，用4染边vw。当?(w1)?C(w)时，取b′=?(w1)。?(w)=4。不妨设C(w)={1,2,4}。令α1∈C\\{1,2,3,4,a}，α2∈C\\{1,2,4,α1,b}，用α1染边uv，α2染边vw。如 =G?v，则H是一个E(H) 断言4的证明完成。 ? 由断言1-4得G是3-正则的。但是根据引理3，G有一个6-严格邻点可区别全染色的，矛盾。 ? 参考文献 [1] Zhang, Z., Chen, X., Li, J., Yao, B., Lu, X. and Wang, J. (2005) On Adjacent-Vertex-Distinguishing Total Coloring of Graphs. Science in China Series A, 48, 289-299. https://doi.org/10.1360/03YS0207 [2] Chen, X. (2008) On the Adjacent Vertex Distinguishing Total Coloring Numbers of Graphs with Δ = 3. Discrete Ma-thematics, 308, 4003-4007. https://doi.org/10.1016/j.disc.2007.07.091 [3] Wang, H. (2007) On the Adjacent Vertex-Distinguishing Total Chromatic Numbers of the Graphs with Δ(G) = 3. DOI: 10.12677/aam.2020.98159 1349 应用数学进展 刘含荃，顾静 Journal of Combinatorial Optimization, 14, 87-109. https://doi.org/10.1007/s10878-006-9038-0 [4] Hulgan, J. (2009) Concise Proofs for Adjacent Vertex-Distinguishing Total Colorings. Discrete Mathematics, 309, 2548-2550. https://doi.org/10.1016/j.disc.2008.06.002 [5] Papaioannou, A. and Raftopoulou, C. (2014) On the AVDTC of 4-Regular Graphs. Discrete Mathematics, 330, 20-40. https://doi.org/10.1016/j.disc.2014.03.019 [6] Lu, Y., Li, J., Luo, R. and Miao, Z. (2017) Adjacent Vertex Distinguishing Total Coloring of Graphs with Maximum Degree 4. Discrete Mathematics, 340, 119-123. https://doi.org/10.1016/j.disc.2016.07.011 [7] Huang, D., Wang, W. and Yan, C. (2012) A Note on the Adjacent Vertex Distinguishing Total Chromatic Number of Graphs. Discrete Mathematics, 312, 3544-3546. https://doi.org/10.1016/j.disc.2012.08.006 [8] 梁少卫. k-方体图的Smarandachely邻点全染色[J]. 唐山学院学报, 2009, 22(3): 6-7. [9] 卫斌, 朱恩强, 文飞, 徐文辉. 圈的平方图的Smarandachely邻点全色数[J]. 惠州学院学报(自然科学版), 2011, 31(6): 13-15. [10] Li, J., Wang, Z., Wen, F. and Zhang, Z. (2010) The Smarandachely Adjacent-Vertex Distinguishing Total Coloring of Two Kind of 3-Regular Graphs. 3rd International Conference on Biomedical Engineering and Informatics, Yantai, 16-18 October 2010, 3004-3006. https://doi.org/10.1109/BMEI.2010.5639827 [11] 时亭亭, 强会英, 文飞. 广义拟Thomassen图的Smarandachely邻点全色数[J]. 兰州交通大学学报, 2010, 29(4): 147-149. [12] Wang, Z., Lee, J., Li, J. and Wen, F. (2011) The Smarandachely Adjacent Vertex Total Coloring of a Kind of 3-Regular Graph. Ars Combinatoria, 99, 45-53. [13] 李沐春, 王立丽, 张伟东, 凌昭昭. 若干类3-正则图的Smarandachely邻点全染色的界[J]. 南开大学学报(自然科 学版), 2014, 47(6): 79-84. [14] 陈妹君, 田双亮. 两类运算图的Smarandachely邻点可区别全染色[J]. 贵州师范大学学报(自然科学版), 2015, 33(1): 73-75. [15] 李春梅, 王治文. Δ(G) ≤ 3的2-连通外平面图的Smarandachely邻点可区别全色数[J]. 大学数学, 2019, 35(3): 1-4. DOI: 10.12677/aam.2020.98159 1350 应用数学进展
子立方图的严格邻点可区别全染色
