子立方图的严格邻点可区别全染色

doi:10.12677/AAM.2020.98159

期刊菜单

子立方图的严格邻点可区别全染色
Strict Neighbor-Distinguishing Total Coloring of Subcubic Graphs

DOI: 10.12677/AAM.2020.98159, PDF, HTML, XML, 下载: 609 浏览: 2,880
作者: 刘含荃, 顾静：浙江师范大学数学与计算机科学学院，浙江金华
关键词: 严格邻点可区别全染色；严格邻点可区别全色数；子立方图；Strict Neighbor-Distinguishing Total Coloring； Strict Neighbor-Distinguishing Total Index； Subcubic Graphs

摘要: 图G的一个正常k-全染色是指一个映射

，使得

中任意两个相邻的或相关联的元素染不同颜色。令C_φ(v)表示点v的颜色与v的关联边的颜色组成的集合。如果满足对任意一条边

都有

和

，则称φ是k-严格邻点可区别的。图G的严格邻点可区别全色数是使G是k-严格邻点可区别全可染的最小正整数k，用χ_snt(G)表示。本文证明了每个子立方图满足

。

Abstract: A proper total k-coloring of a graph G is a mapping

, such that any two adjacent or incident elements in

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

and

for each edge

. The strict neighbor-distin- guishing total index, denoted by χ_snt(G), of G is the minimum integer k such that G is k-strict neighbor-distinguishing total colorable. In this paper, we prove that every subcubic graph G has

文章引用：刘含荃, 顾静. 子立方图的严格邻点可区别全染色[J]. 应用数学进展, 2020, 9(8): 1346-1350. https://doi.org/10.12677/AAM.2020.98159

1. 引言

本文只考虑有限简单图，设G是一个点集为V(G)，边集为E(G)的图，它的最大度，最小度分别为Δ(G)，δ(G)。当点v的度是k时，称为k-点。令N_G(v)代表与v相邻的点集。很容易得到对简单图G中的任一点v，有 $d_{G} (v) = | N_{G} (v) |$ 。在不会混淆的情况下，Δ(G)，δ(G)，d_G(v)和N_G(v)分别可以写成Δ，δ，d(v)和N(v)。令P_n和C_n分别表示阶为n的路和阶为n的圈。如果图G的每个点的度都是一个固定的常数k，则称G是k-正则的。一个图G如果是3-正则的，则称为立方图；如果满足 $Δ (G) \leq 3$ ，则称为子立方图。图G如果满足 $δ (G) \geq 2$ ，则称G为正常的。

图G的一个正常k-全染色是指一个映射 $φ : V (G) \cup E (G) \to {1, 2, \dots, k}$ ，使得对任意两个相邻的或相关联的元素 $z_{1}, z_{2} \in V (G) \cup E (G)$ ，有 $φ (z_{1}) \neq φ (z_{2})$ 。设 $C_{φ} (v) = {φ (v} \cup {φ (e) : e \in E_{G} (v)}$ 。如果对任意一对相邻的点u和v，有 $C_{φ} (u) \neq C_{φ} (v)$ ，我们把φ称为邻点可区别的。图G的邻点可区别全色数X_at(G)是使G有一个k-邻点可区别全染色的最小正整数k。此外，如果对任意一对相邻的点u和V，有 $| C_{φ} (u) \ C_{φ} (v) | \geq 1$ 和 $| C_{φ} (v) \ C_{φ} (u) | \geq 1$ ，我们称φ为严格邻点可区别的。图G的严格邻点可区别全色数χ_at(G)是使G有一个k-严格邻点可区别全染色的最小正整数k。

2005年，张忠辅等人在 [1] 中首先给出了图的邻点可区别全染色的概念，并且对圈、完全图、完全二部图、扇、轮图和树的邻点可区别全染色展开研究，确定了它们的邻点可区别全色数，并根据特殊图的邻点可区别全色数提出了如下猜想：

猜想1 [1] 对于阶不少于2的简单连通图G，有 $χ_{a t} (G) \leq Δ (G) + 3$ 。

如果猜想1成立，则这个上界是紧的。例如，对于任意正整数 $t \geq 1$ ，有 $χ_{a t} (K_{2 t + 1}) = 2 t + 1 + 2 = Δ (K_{2 t + 1}) + 3$ 。Chen和Wang分别在 [2] 和 [3] [4] 中证明了 $Δ = 3$ 的连通图满足猜想1。奇数阶的完全图的邻点可区别全色数可以达到猜想1的上界，由于奇数阶的完全图的最大度为偶数，但是对于 $Δ = 3$ 的连通图，上界6是否是紧的这一问题至今仍未解决。Papaioannou和Raftopoulou在 [5] 中从算法的角度证明了所有的4-正则图G，有 $χ_{a t} (G) \leq 7$ ，是满足猜想1的。Lu等人在 [6] 中运用组合零点定理证明了所有 $Δ = 4$ 的连通图G，有 $χ_{a t} (G) \leq 7$ ，是满足猜想1的。Huang，Wang和Yan在 [7] 中把 $Δ \geq 3$ 的图的邻点可区别全色数的上界改进到2Δ(G)。

严格邻点可区别全染色(被命名为Smarandachely邻点可区别全染色)有及以下猜想。

猜想2 对于阶不小于2的简单连通图G，有 $χ_{s n t} (G) \leq Δ (G) + 3$ 。

2009年，梁少卫在 [8] 中证明了 $k \geq 2$ 的k-正则偶图和k-方体图Q_k，满足猜想2。2011年，卫斌等人在 [9] 中证明了圈的平方图，满足猜想2。文献 [10] [11] [12] [13] 中给出了若干类的3-正则图的严格邻点可区别全色数均为5，满足猜想2。2015年，陈妹君等人在 [14] 中研究了Mycielski图的严格邻点可区别全色数满足猜想2。2019年，李春梅等人在 [15] 证明了 $Δ \leq 3$ 的2-连通外平面图满足猜想2。

2. 主要结果

在展示主要结果前，我们先建立一些有用的观察。首先，根据定义，以下式子显然成立。

引理1 [2] 如果图G是一个 $Δ = 3$ 的图，则G有一个6-邻点可区别全染色。

引理2 对 $r \geq 2$ ，每个r-正则图G满足 $χ_{s n t} (G) = χ_{a t} (G)$ 。

结合引理1和2，我们得到以下事实：

引理3 如果图G是一个3-正则图，则 $χ_{s n t} (G) \leq 6$ 。

引理4 对一个阶为n的圈C_n，有 $χ_{s n t} (G) = 4$ 。

引理5 对 $P_{n} (n \geq 2)$ ，有 $χ_{s n t} (P_{n}) = 4$ 。

证明：设 $P_{n} = v_{1} v_{2} \dots v_{n}, n \geq 2$ ，连接v₁和v_n得到一个圈C_n。设 $C = {1, 2, 3, 4}$ 是一个颜色集合。由引理4，C_n有一个4-严格邻点可区别全染色φ。除了点v₁和v_n，用与C_n相同的颜色染P_n中的点和边，设 $α \in C \ C_{φ} (v_{2})$ ， $β \in C \ C_{φ} (v_{n - 1})$ ，用α染点v₁，用β染点v_n。 £

定理1 如果图G是一个正常的子立方图，则 $χ_{s n t} (G) \leq 6$ 。

证明：我们用反证法证明。设 $C = {1, 2, \dots, 6}$ 是一个颜色集合。假设图G是一个边数 $| E (G) |$ 最小的极小反例。如果 $| E (G) | \leq 6$ ，则定理成立，因为足以给每条边分配不同的颜色。所以假设G是一个 $Δ \leq 3$ ， $| E (G) | \geq 7$ 的图，且G无法用C中的颜色染好。

如果 $Δ = 2$ ，G是一个圈或一条路，由引理4和引理5，有 $χ_{s n t} (G) \leq 6$ 。所以假设 $Δ = 3$ 。为了完成证明，我们需要构造以下一系列的断言。在断言的证明中，我们用C(v)代替C_φ(v)。

断言1 G不包含1-点。

证明：反之，G包含一个1-点v。设点u是v的邻点。如果 $d (u) = 2$ ，设 $N (u) = {v, u_{1}}$ ；如果 $d (u) = 3$ ，设 $N (u) = {v, u_{1}, u_{2}}$ 。令 $H = G - v$ ，则H是一个 $| E (H) | < | E (G) |$ 且 $Δ (H) \leq Δ (G)$ 的图。所以H存在一个6-严格邻点可区别全染色φ，其所用颜色集合为C。

对 $i \in {1, 2}$ ，如果 $| C (u_{i}) \ C (u) | = 1$ ，取 $a_{i} \in C (u_{i}) \ C (u)$ 。令 $α \in C \ C (u) \cup {a_{1}, a_{2}}$ ，用α染边uv。令 $β \in C \ C (u) \cup {α}$ ，用β染点v。断言1的证明完成。 £

断言2 G不包含相邻2-点。

证明：反之，G包含两个相邻2-点u和v。设 $N (u) = {v, u_{1}}$ ， $N (v) = {u, v_{1}}$ 。令 $H = G - u v$ ，则H是一个 $| E (H) | < | E (G) |$ 且 $Δ (H) = Δ (G) = 3$ 的图。所以H存在一个6-严格邻点可区别全染色φ，其所用颜色集合为C。

先假设 $C (u) = C (v)$ 。己知 $| C (v_{1}) \cup C (v) | \leq 5$ ，令 $α \in C \ C (v_{1}) \cup C (v)$ ，用α改染点v。令 $β \in C \ C (u) \cup {a}$ ，用β染边uv。因此 $C (u) \neq C (v)$ 。如果 $φ (u) = φ (v)$ ，令 $α \in C \ C (v_{1}) \cup C (v)$ ，用α改染点v。令 $β \in C \ C (u) \cup {α, φ (v v_{1})}$ ，用β染边uv。如果 $φ (u) \neq φ (v)$ ，令 $β \in C \ C (u) \cup 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) | < | E (G) |$ 的图。所以H存在一个6-严格邻点可区别全染色φ，其所用颜色集合为C。

情形1. $| C (u) \cup C (x) \cup C (y) | < 6$ 。

令 $α \in C \ C (u) \cup C (x) \cup C (y)$ ，用α染点v。集合C\{α}中必定存在一个在C(u)，C(x)，C(y)中至多用了一次的颜色，不妨设为1。

如果 $1 \notin C (u) \cup C (x) \cup C (y)$ ，用1染边uv。令 $β_{1} \in C \ C (x) \cup {1, α}$ ，用β₁染边vx。当 $β_{1} \notin C (u)$ ，因为 $| C (y) \cup {1, α, β_{1}} | \leq 5$ ，令 $β_{2} \in C \ C (y) \cup {1, α, β_{1}}$ ，用β₂染边vy。当 $β_{1} \in C (u)$ ，删去边uv的颜色，用1染边vy。设 $C^{'} (v) = {1, α, β_{1}}$ ， $C^{'} (y) = C (y) \cup {1}$ 。如果 $| C' (y) \ C' (v) | = 1$ ，取 $a_{1} \in C' (y) \ C' (v)$ ，因为 $| C (u) \cup {1, α, a_{1}} | \leq 5$ ，令 $β_{2} \in C \ C (u) \cup {1, α, a_{1}}$ ，用β₂染边uv。

如果 $1 \in C (u)$ (或C(x)，或C(y))，假设 $C (u) = {1, 2}$ 。用1染边vx，因为 $| C (y) \cup {1, 2, α} | \leq 5$ ，令 $β_{1} \in C \ C (y) \cup {1, 2, α}$ ，用β₁染边vy。设 $C^{'} (v) = {1, α, β_{1}}$ ， $C' (x) = C (x) \cup {1}$ 。如果 $| C^{'} (x) \ C^{'} (v) | = 1$ ，取 $a_{2} \in C^{'} (x) \ C^{'} (v)$ ，因为 $| C (u) \cup {β_{1}, α, a_{2}} | \leq 5$ ，令 $β_{2} \in C \ C (u) \cup {β_{1}, α, a_{2}}$ ，用β₂染边uv。

情形2. $| C (u) \cup C (x) \cup C (y) | = 6$ 。

设 $N (u) = {v, u_{1}}$ ，则 $d (u_{1}) = 3$ 。因为 $| C (u_{1}) \cup C (u) | \leq 5$ ，令 $α \in C \ C (u_{1}) \cup C (u)$ ，用α改染点u。此时 $C (u) \cup C (x) \cup C (y) \neq C$ ，根据情形1，G有一个6-严格邻点可区别全染色。

断言3的证明完成。 £

断言4 G中2-点不与3-点相邻。

证明：反之，G包含相邻的3-点u和2-点v，设 $N (v) = {u, w}$ ，因此w是一个3-点。设 $N (u) = {v, u_{1}, u_{2}}$ ， $N (w) = {v, w_{1}, w_{2}}$ 。u₁，u₂，w₁，w₂是2-点或3-点。由断言3，u₁或u₂是3-点，w₁或w₂是3-点。不妨设 $d (u_{2}) = 3$ ， $d (w_{2}) = 3$ 。令 $H = G - v$ ，则H是一个 $| E (H) | < | E (G) |$ 的图。所以H存在一个6-严格邻点可区别全染色φ，其所用颜色集合为C。如果 $| C (u_{1}) \ C (u) | = 1$ ，取 $a \in C (u_{1}) \ C (u)$ 。如果 $| C (w_{1}) \ C (w) | = 1$ ，取 $b \in C (w_{1}) \ C (w)$ 。设 $C (u) = {1, 2, 3}$ 。

情形1. $| C (u) \cap C (w) | = 3$ 。

设 $α_{1} \in C \ {1, 2, 3, a}$ ，用α₁染边uv。设 $α_{2} \in C \ {1, 2, 3, α_{1}, b}$ ，用α₂染边vw。设 $α_{3} \in C \ {α_{1}, α_{2}, φ (u), φ (w)}$ ，用α₃染点v。

情形2. $| C (u) \cap C (w) | = 2$ 。

不妨设 $C (w) = {1, 2, 4}$ 。令 $α_{1} \in C \ {1, 2, 3, 4, a}$ ， $α_{2} \in C \ {1, 2, 4, α_{1}, b}$ ，用α₁染边uv，α₂染边vw。如果 $α_{2} = 3$ ，令 $α_{3} \in C \ {1, 2, 3, α_{1}, φ (w)}$ ，用α₃染点v。如果 $α_{2} \neq 3$ ，令 $α_{3} \in C \ {α_{1}, α_{2}, φ (u), φ (w)}$ ，用α₃染点v。

情形3. $| C (u) \cap C (w) | = 1$ 。

不妨设 $C (w) = {1, 4, 5}$ 。令 $α_{1} \in {4, 5} \ {a}$ ， $α_{2} \in {2, 3} \ {b}$ ，用α₁染边uv，α₂染边vw，6染点v。

情形4. $| C (u) \cap C (w) | = 0$ 。

不妨设 $C (w) = {4, 5, 6}$ ， $φ (w) = 4$ 。删去点w的颜色，用4染边vw。当 $φ (w_{1}) \notin C (w)$ 时，取 $b^{'} = φ (w_{1})$ 。当 $φ (w_{1}) \in C (w)$ 时，取 $b^{'} \in C (w_{1}) \ C (w)$ 。令 $α_{1} \in C \ {4, 5, 6, b^{'}, φ (w_{2})}$ ，用α₁染点w。显然， $α_{1} \in {1, 2, 3}$ 。令 $α_{2} \in {5, 6} \ {a}$ ， $α_{3} \in C \ {4, 5, 6, α_{1}, φ (u)}$ ，用α₂染边uv，α₃染点v。

断言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 Mathematics, 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. 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.

为你推荐

友情链接