最大度为3的符号图的全染色
Total Coloring of Signed Graphs with Maximum Degree 3
DOI: 10.12677/AAM.2020.910195, PDF, HTML, XML, 下载: 652  浏览: 2,951 
作者: 王 超：浙江师范大学，数学与计算机科学学院，浙江 金华
关键词: 符号图；全染色；最大度；Signed Graph； Total Coloring； Maximum Degree
摘要: 在图G=(V,E)中，使得相邻和相关联的元素均染不同颜色的染色方法，称为图G的正常全染色。使得G为正常全染色的最少颜色数，称为G的全色数，记为XT(Γ)。在本文中，我们给出全染色在符号图中的定义，并在最大度为3的符号图中证明了全色数的上界为5。
Abstract: For graph G=(V,E), a proper total coloring is a coloring of V and E such that no two adjacent or incident elements get the same color. The total chromatic number of G, denoted by XT(Γ), is the smallest integer k such that G have a proper total coloring. In this paper, we give a definition of total coloring in signed graphs, and prove the total chromatic number is 5 in signed graph with maximum degree 3.
文章引用：王超. 最大度为3的符号图的全染色[J]. 应用数学进展, 2020, 9(10): 1686-1692. https://doi.org/10.12677/AAM.2020.910195

1. 引言

图的染色问题是图论的主要研究问题之一，图的染色一般分为点染色，边染色，全染色和其他特定的染色。本文中提到的图 G = ( V , E ) 均为简单图，V(G)，E(G)，Δ(G)分别表示图G的顶点集合和边集合，简记为V，E，Δ。如果 x ∈ V ( G ) ， e ∈ E ( G ) ， G − x 表示从图G去掉点x及和点x相关联的边， G − e 则表示从图G中去掉边e。

定义1.1 在图 G = ( V , E ) 中，对点和边同时进行染色，并且当相邻和相关联的元素均染不同颜色的染色方法，称为图G的正常全染色，使得图G为正常全染色的最少颜色数，称为图G的全色数，记为 χ T ( G ) 。

当我们对图 G = ( V , E ) 进行全染色时，因为要同时考虑点和边，在确定全色数时要比确定色数和边色数更困难。根据上述定义，显然 χ T ( G ) ≥ Δ + 1 。Behzad [1] 在1965年提出了著名的全染色猜想(TTC)：对任意的图G， χ T ( G ) ≤ Δ + 2 。

在1969年，Vijayaditya [2] 证明了 Δ ≤ 3 时全染色猜想成立，之后Vostochka [3] 证明了 Δ ≤ 5 时全染色猜想成立。

在本文中，我们给出全染色在符号图中的定义，并在最大度为3的符号图中给出了全色数的上界。符号图是Harary [4] 在1953年提出：一个符号图 Γ = ( G , σ ) 是在图G的基础上，对其边集E(G)加上符号 σ : { E ( G ) → + 1 , − 1 } ，G称为 Γ = ( G , σ ) 的基础图。在符号图 Γ = ( G , σ ) 中，对任意的一条边e，如果 σ ( e ) = 1 ，则称e是正边；如果 σ ( e ) = − 1 ，则称e是负边。符号颜色 M n = { 0 , ± 1 , ± 2 , ⋯ , ± n } 当 n = 2 k + 1 ； M n = { ± 1 , ± 2 , ⋯ , ± n } 当 n = 2 k 。我们称 M n 为符号颜色集，在 M n 中颜色±1是两个不同但互为相反的颜色。在图 G = ( V , E ) 中一个incidence表示 ( v , e ) : v ∈ V , e ∈ E ，v是e的一个顶点。I(G)表示图 G = ( V , E ) 中所有的incidence，此时我们有 | I ( G ) | = 2 | E ( G ) | 。现在我们给出符号图中全染色的定义：

定义1.2 在符号图 Γ = ( G , σ ) 中，一个全染色f是用颜色集 M n 中的颜色同时对符号图Γ中的incidence和点进行染色，并且如果f满足下面的三个条件：

(1) 对任意的 e = u v ， f ( u ) ≠ σ e f ( v ) ， f ( u , e ) = σ e f ( v , e ) ， σ e 表示边e的符号；

(2) 对任意的 e 1 = u v ， e 2 = v w ， f ( v , e 1 ) ≠ f ( v , e 2 ) ；

(3) 对任意的 v ∈ V ( Γ ) ，v是e的一个顶点， f ( v ) ≠ f ( v , e ) 。

此时称f为符号图 Γ = ( G , σ ) 的正常全染色，使得Γ为正常全染色的最少颜色数，称为Γ的全色数，记为 χ T ( Γ ) 。如果 f ( x ) = a 或 f ( x , x y ) = a ，则称在点x上颜色a存在。否则称在点x上缺少颜色a。

此时，我们可以看出当符号图 Γ = ( G , σ ) 中所有边都是正边时，定义1.1和1.2相同，所以定义1.1是定义1.2的一个特殊情况。根据定义1.2，我们有对任意的符号图Γ， χ T ( Γ ) ≥ Δ + 1 ，Δ表示图Γ的最大度。在本文中我们给出了最大度为3的符号图中全色数的上界。

定理1 如果 Γ = ( G , σ ) 是最大度为3的符号图，则 χ T ( Γ ) ≤ 5 。

2. 定理1的证明

在证明定理1之前，我们需要一些准备工作，首先考虑符号图 Γ = ( G , σ ) 中的圈 C n : x 1 x 2 ⋯ x n x n + 1 = x 1 ，我们对 C n 做如下特殊的全染色，记为 ℜ 。

情况1：如果 C n 有偶数条正边，则

ℜ ( x 1 ) = 1 ℜ ( x i + 1 ) = − ℜ ( x i ) 当 x i x i + 1 为 正 边 ℜ ( x i + 1 ) = ℜ ( x i ) 当 x i x i + 1 为 负 边 ℜ ( x 1 , x 1 x 2 ) = 2 ℜ ( x i + 1 , x i x i + 1 ) = ℜ ( x i , x i x i + 1 ) 当 x i x i + 1 为 正 边 ℜ ( x i + 1 , x i x i + 1 ) = − ℜ ( x i , x i x i + 1 ) 当 x i x i + 1 为 负 边 ℜ ( x i + 1 , x i + 1 x i + 2 ) = − ℜ ( x i + 1 , x i x i + 1 ) 1 ≤ i ≤ n

情况2：如果 C n 有奇数条正边，则

ℜ ( x 1 ) = 1 ℜ ( x i + 1 ) = − ℜ ( x i ) 当 x i x i + 1 为 正 边 ℜ ( x i + 1 ) = ℜ ( x i ) 当 x i x i + 1 为 负 边 ℜ ( x 1 , x 1 x 2 ) = 2 ℜ ( x i + 1 , x i x i + 1 ) = ℜ ( x i , x i x i + 1 ) 当 x i x i + 1 为 正 边 ℜ ( x i + 1 , x i x i + 1 ) = − ℜ ( x i , x i x i + 1 ) 当 x i x i + 1 为 负 边 ℜ ( x i + 1 , x i x i + 1 ) = − ℜ ( x i + 1 , x i + 1 x i + 2 ) 1 ≤ i ≤ n − 1 对 x n 和 x n x 1 ℜ ( x n ) = − ℜ ( x n , x n x n − 1 ) ℜ ( x 1 , x n x 1 ) = − ℜ ( x 1 )

此时，我们称上述在圈 C n 上的染色方法为特殊染色，根据上述的特殊染色，我们可以得出在最大度为2的符号图Γ中， χ T ( Γ ) ≤ 4 。因为当Γ是一条路时，对其点用颜色±1进行染色，其边用±2进行染色。在正边个数为奇数的圈 C n 中，我们称点 x 1 ， x n − 1 和点 x n 为特殊点。不难看出，如果 ℜ 是圈 C n 上的特殊染色，对非特殊点 x i 来说，我们交换点 x i 和incidence ( x i , x i x i + 1 ) 的颜色并根据边 x i x i + 1 的符号确定 ( x i + 1 , x i x i + 1 ) 的颜色，交换后 ℜ 仍然是 C n 的正常全染色。

现在我们根据上述在圈中的特殊全染色 ℜ 来证明定理1，首先证明下面的相关引理。

引理2.1 符号图 Γ = ( G , σ ) 是最大度为3的连通图，如果 Γ = ( G , σ ) 不是3-正则的，则 χ T ( Γ ) ≤ 5 。

证明：对符号图Γ的点数做归纳，因为符号图Γ不是3-正则的，因此Γ有一个点x使得 d ( x ) ≤ 2 ，当点数为1，2，3时，该结果显然成立。现在假设图Γ的点数大于3，对符号图 Γ − x ，根据归纳假设， Γ − x 有一个正常的5-全染色f，其颜色为 { ± a , ± b , c } 。现在我们将用相同的5个颜色把f扩展为图Γ上的正常全染色，我们分为两个情况讨论：

情况1： 如果 d ( x ) = 1 ， x y ∈ E ( Γ ) ，在 Γ − x 中，颜色 { ± a , ± b } 中至少有一个颜色在点y上没有使用，设为a，此时用颜色a对incidence ( y , x y ) 染色并根据边xy的符号对 ( x , x y ) 和点x染色，不妨假设边xy为正边， f ( y ) = b ，因此我们可用颜色a对 ( x , x y ) 染色，用颜色c对点x染色。

情况2： 如果 d ( x ) = 2 ， x y , x z ∈ E ( Γ ) ，根据归纳假设符号图 Γ − x 有正常的5-全染色f，因此点y和点z至少分别缺少两个颜色，我们不妨考虑点y和点z分别缺少两个颜色的情况，此时在符号图Γ中 d ( y ) = d ( z ) = 3 。

情况2.1：点y和点z缺少的两个颜色相同

情况2.1.1：当缺少的两个颜色为相反颜色时，记为 { ± a } ，此时用颜色a对incidence ( y , x y ) 染色，根据边xy的符号对 ( x , x y ) 染色，再用与 ( x , x y ) 相反的颜色对 ( x , x z ) 染色，根据边xz的符号对 ( z , x y ) 染色，例如： f ( y , x y ) = f ( x , x y ) = a ，则 f ( x , x z ) = − a ， f ( z , x z ) = − a 当边xz为正边，否则 f ( z , x z ) = a ，现在考虑点x，因为incidence ( x , x y ) ， ( x , x z ) ，点y和点z至多使用四个不同的颜色，再根据边xy和xz的符号即可对点x进行染色。

情况2.1.2：当缺少的两个颜色不相反时，记为 { a , b } ，此时分别用颜色a和b对incidence ( y , x y ) 和 ( z , x z ) 染色，根据边xy和xz的符号对 ( x , x y ) ， ( x , x z ) 染色，对于点x，可采用情况2.1.1中对点x的方法染色。

情况2.2：点y和点z缺少两个颜色至多一个相同，记为a，此时我们可以在点y和点z缺少的颜色中找出两个颜色既不相同又不相反的颜色，不妨记为 { − a , b } ，此时分别用颜色-a和b对incidence ( y , x y ) 和 ( z , x z ) 染色，根据边xy和xz的符号对 ( x , x y ) ， ( x , x z ) 染色，对于点x，仍旧采用情况2.1.1中对点x的方法染色，该引理得证。

引理2.2 符号图 Γ = ( G , σ ) 是连通的3-正则图，如果 Γ = ( G , σ ) 包含割边 e = u v ，则 χ T ( Γ ) ≤ 5 。

证明：因为 e = u v 是符号图Γ的一条割边，则 Γ − e 有两个连通分支 Γ 1 和 Γ 2 ， u ∈ Γ 1 ， v ∈ Γ 2 ，因此 d Γ 1 ( u ) = d Γ 2 ( v ) = 2 ，根据引理2.1， Γ 1 和 Γ 2 分别有正常的5-全染色 f 1 和 f 2 。

情况1：如果 e = u v 是正边，通过对 f 1 和 f 2 中的颜色进行排列调整，使得

(1) f 1 ( u ) ≠ f 2 ( v ) ；

(2) 在 Γ 1 中与点u相关联的两个incidence的颜色和在 Γ 2 中与点v相关联的两个incidence的颜色相同。

此时，对 e = u v 上的两个incidence可用第五种颜色染色，现在我们便可以将 f 1 和 f 2 组合并将其扩展为符号图 Γ 上的一个正常的5-全染色f。

情况2：如果 e = u v 是负边，通过对 f 1 和 f 2 中的颜色进行排列调整，使得

(1) f 1 ( u ) = f 2 ( v ) = c ；

(2) 在 Γ 1 中与点u相关联的两个incidence的颜色和在 Γ 2 中与点v相关联的两个incidence的颜色相同，并且使用的两个颜色相反。

类似的，对 e = u v 上的两个incidence可用剩余的两个相反颜色染色，现在便可将 f 1 和 f 2 组合并将其扩展为 Γ 上的一个正常的5-全染色f，该引理得证。

在图 G = ( V , E ) 中，对集是没有公共顶点的边集合，当对集M覆盖图G中的所有点时，称M为完美对集或1-因子。

引理2.3 [5] 如果G是没有割边的3-正则图，则G的边集可分解为1-因子和边不交的圈的并集。

在符号图中，我们可以看出引理2.3仍然成立，我们将借助引理2.3来证明下面的引理。

引理2.4 符号图 Γ = ( G , σ ) 是连通的3-正则图，如果符号图 Γ 不包含割边 e = u v ，则 χ T ( Γ ) ≤ 5 。

证明：根据引理2.3，我们有 E ( Γ ) 可以分解为1-因子F和边不交的圈 C 1 , C 2 , C 3 , ⋯

首先，我们对圈 C 1 , C 2 , C 3 , ⋯ 中的点做标号： C i : x 1 i x 2 i ⋯ x n i i x 1 i ，同时设计如下算法：

算法1：对任意的两个正边个数为奇数的圈 C i 和 C j 满足

x 1 i x 1 j , x n i − 1 i x n j − 1 j ∉ E ( Γ ) (1)

步骤1：如果 C 1 , C 2 , C 3 , ⋯ 中没有正边数为奇数的圈，对每一个圈 C i 的点标号 C i : x 1 i x 2 i ⋯ x n i i x 1 i ，如果 Γ 含有正边数为奇数的圈 C 1 , C 2 , ⋯ 我们标记 C 1 中的一个顶点为 x 1 1 。

步骤2：如果 x 1 1 与正边个数为奇数的未标号圈的顶点相邻，我们进行步骤3，如果 x 1 1 不相邻正边个数为奇数的未标号圈的顶点，我们在以点 x 1 1 起点的两个方向中选择任意一个方向对圈 C 1 中的其他点进行标号。此时，如果 x n 1 − 1 1 与正边个数为奇数的未标号圈的顶点相邻，我们进行步骤4，否则，我们回到步骤1，对未标号的圈继续做顶点标号。

步骤3：如果 x 1 1 与正边个数为奇数的未标号圈的顶点相邻，并将这个圈重新编号为 C 2 ，在 C 2 中与点 x 1 1 相邻的点记为 x n 2 − 1 2 并在以点 x n 2 − 1 2 起点的两个方向中任选一个方向对 C 2 中的其他点进行标号，此时我们回到步骤2考虑点 x 1 2 。

步骤4：如果 x 1 1 不相邻正边个数为奇数的未标号圈的顶点但是 x n 1 − 1 1 与正边个数为奇数的未标号圈的顶点相邻，记为y，我们将这个圈重新编号为 C 2 并将y标号为 x 1 2 ，再以点 x 1 2 起点的两个方向中选择任意一个方向对圈 C 2 中的其他点进行标号，此时，我们回到步骤2考虑点 x n 2 − 1 2 。

步骤5：因为图Γ是有限的，该算法最终会结束。我们从一个正边个数为奇数的未标号圈开始，重复步骤2的整个过程，我们可以对所有的正边个数为奇数的圈中的点完成标号，对正边个数为偶数的圈中的点我们可以对其选择任意标号。

现在我们根据对每一个圈 C i 中点的标号 C i : x 1 i x 2 i ⋯ x n i i x 1 i 和算法1的结果对符号图Γ做全染色。在符号图Γ中，圈 C 1 , C 2 , C 3 , ⋯ 是Γ上的所有圈，令f是圈 C 1 , C 2 , C 3 , ⋯ 的特殊染色，使用的颜色为 { ± 1 , ± 2 } ，现在我们将f扩展为符号图Γ上5-全染色，其颜色集扩充为 { ± 1 , ± 2 , 3 } 。任取 x h k x q p ∈ F 。

情况1： x h k x q p 是正边。

情况1.1：如果 f ( x h k ) ≠ f ( x q p ) ，用颜色3对 ( x h k , x h k x q p ) 和 ( x q p , x h k x q p ) 进行染色。

情况1.2：如果 f ( x h k ) = f ( x q p ) 。

情况1.2.1：如果点 x h k 和 x q p 中有一个点不是特殊点，不妨设为 x h k 。此时用颜色3对 ( x h k , x h k x q p ) 和 ( x q p , x h k x q p ) 染色并交换点 x h k 和incidence ( x h k , x h k x h + 1 k ) 的颜色，再根据边 x h k x h + 1 k 的符号确定 ( x h + 1 k , x h k x h + 1 k ) 的颜色。

情况1.2.2：如果点 x h k 和 x q p 都是特殊点，根据算法1， x h k x q p 可能是 x n k k x n p p ， x 1 k x n p − 1 p 和 x n k − 1 k x 1 p 。当 x h k x p p = x n k k x n p p ，根据特殊染色f，不妨令 f ( x h k ) = f ( x q p ) = 2 ，此时我们有边 x n k k x 1 k 和边 x n p p x 1 p 有相同的符号，否则的话会与 f ( x h k ) = f ( x q p ) 矛盾。如果边 x n k k x 1 k 和 x n p p x 1 p 边都是正边，f是特殊染色，因此 ( x n k k , x n k k x 1 k ) 和 ( x 1 k , x n k k x 1 k ) 的颜色都是−1。现在我们用颜色3对点 x q p 重新染色并用颜色1对 ( x q p , x h k x q p ) 和 ( x h k , x h k x q p ) 染色。如果边 x n k k x 1 k 和 x n p p x 1 p 边都是负边，可做类似处理。此时， f ( x 1 k , x n k k x 1 k ) = − 1 ， f ( x n k k , x n k k x 1 k ) = 1 ，用颜色3对点 x q p 重新染色并用颜色−1对 ( x q p , x h k x q p ) 和 ( x h k , x h k x q p ) 染色，该情况得证。

当 x h k x q p = x 1 k x n p − 1 p 或者 x h k x q p = x n k − 1 k x 1 p ，这两种情况类似，我们介绍 x h k x q p = x 1 k x n p − 1 p 时的情况，根据特殊染色f， f ( x 1 k ) = f ( x n p − 1 p ) = 1 并且边 x n p p x 1 p 和边 x n p − 1 p x n p p 有相反的符号，令 x n p − 1 p x n p p 是正边， x n p p x 1 p 是负边。因此 f ( x 1 p , x n p p x 1 p ) = − 1 ， f ( x n p p , x n p p x 1 p ) = 1 ， f ( x n p p , x n p p x n p − 1 p ) = 2 ， f ( x n p − 1 p , x n p p x n p − 1 p ) = 2 ， f ( x n p p ) = − 2 。下面考虑边 x n p − 1 p x n p − 2 p 的符号：

如果 x n p − 1 p x n p − 2 p 是正边，则 f ( x n p − 1 p , x n p − 1 p x n p − 2 p ) = f ( x n p − 2 p , x n p − 1 p x n p − 2 p ) = − 2 ， f ( x n p − 2 p ) = − 1 ，此时交换点 x n p − 2 p 和incidence ( x n p − 2 p , x n p − 1 p x n p − 2 p ) 得到染色 f 1 。因为 x n p − 2 p 不是特殊点， f 1 是正常的全染色， f 1 ( x n p − 2 p ) = − 2 ， f 1 ( x n p − 1 p , x n p − 2 p x n p − 1 p ) = f 1 ( x n p − 2 p , x n p − 2 p x n p − 1 p ) = − 1 。现在 f 1 的基础上再次交换点 x n p − 1 p 和incidence ( x n p − 1 p , x n p − 2 p x n p − 1 p ) 的颜色得到染色 f 2 ，则 f 2 ( x n p − 1 p ) = − 1 ， f 2 ( x n p − 1 p , x n p − 2 p x n p − 1 p ) = f 2 ( x n p − 2 p , x n p − 2 p x n p − 1 p ) = 1 ，现在用颜色3对 ( x 1 k , x 1 k x n p − 1 p ) 和 ( x n p − 1 p , x 1 k x n p − 1 p ) 进行染色，该情况得证。如果 x n p − 1 p x n p − 2 p 是负边，用上述方法做类似处理。

情况2： x h k x q p 是负边。

情况2.1：如果 f ( x h k ) = f ( x q p ) 。

情况2.1.1：如果点 x h k 和 x q p 中有一个点不是特殊点，不妨设为 x h k 。根据特殊染色f，不妨令 f ( x h k ) = f ( x q p ) = 1 ，用颜色3对点 x q p 重新染色，用颜色1对 ( x q p , x h k x q p ) 染色，用颜色−1对 ( x h k , x h k x q p ) 染色。

情况2.1.2：如果点 x h k 和 x q p 中都是特殊点，根据算法1， x h k x q p 可能是 x n k k x n p p ， x 1 k x n p − 1 p 和 x n k − 1 k x 1 p 。当 x h k x p p = x n k k x n p p ，不妨令 f ( x h k ) = f ( x q p ) = 2 ，同样的，边 x n k k x 1 k 和边 x n p p x 1 p 有相同的符号，如果边 x n k k x 1 k 和边 x n p p x 1 p 都为正边，则边 x n k k x 1 k 和边 x n p p x 1 p 上incidence的颜色都是−1。用颜色3对 ( x n k k , x n k k x 1 k ) 和 ( x 1 k , x n k k x 1 k ) 染色，用颜色1对 ( x q p , x h k x q p ) 染色，用颜色−1对 ( x h k , x h k x q p ) 染色。如果边 x n k k x 1 k 和边 x n p p x 1 p 都是负边时，考虑边 x n k k x n k − 1 k 和边 x n p p x n p − 1 p ，如果二者有一个是正边，不妨设为 x n k k x n k − 1 k ，此时用颜色3对 ( x n k k , x n k k x n k − 1 k ) ， ( x n k − 1 k , x n k k x n k − 1 k ) 和 x n p p 重新染色，用颜色2对 ( x n p p , x n p p x n k k ) 染色，用颜色−2对 ( x n k k , x n p p x n k k ) 染色。如果边 x n k k x n k − 1 k 和边 x n p p x n p − 1 p 都是负边，用颜色3对 x n p − 1 p 和 x n k k 重新染色，f是特殊染色并且 x n p p x 1 p 是负边，则 f ( x n p p , x n p p x 1 p ) = 1 ，用颜色1对 ( x n p − 1 p , x n p p x n p − 1 p ) 重新染色，用颜色−1对 ( x n p p , x n p p x n p − 1 p ) 重新染色，此时我们可以用颜色2对 ( x n k k , x n p p x n k k ) 染色，用颜色−2对 ( x n p p , x n p p x n k k ) 染色，得证。

当 x h k x q p = x 1 k x n p − 1 p 或者 x h k x q p = x n k − 1 k x 1 p ，这两种情况类似，我们介绍 x h k x q p = x 1 k x n p − 1 p 时的情况，根据特殊染色f， f ( x h k ) = f ( x q p ) = 1 ，此时用颜色3对点 x h k 重新染色，用颜色1对 ( x h k , x h k x q p ) 染色，因为边 x h k x q p 是负边，用颜色−1对 ( x q p , x h k x q p ) 染色。

情况2.2： f ( x h k ) ≠ f ( x q p ) 。

情况2.2.1：如果点 x h k 和 x q p 中有一个点不是特殊点，不妨设为 x h k 。用颜色3对点 x h k 和 x q p 重新染色，当 q ≠ n p 时用颜色 f ( x q p ) 对 ( x q p , x h k x q p ) 染色，此时，根据边 x h k x q p 的符号，对其上的另一个incidence ( x h k , x h k x q p ) 用颜色1或−1染色，而 x h k 不是特殊点，和它相关联的两个incidence的颜色为±2，因此该情况得证。当 q = n p 时，用颜色 − f ( x q p , x q p x 1 p ) 对 ( x q p , x h k x q p ) 染色，根据边 x h k x q p 的符号对 ( x h k , x h k x q p ) 染色，该情况得证。

情况2.2.2：如果点 x h k 和 x q p 中都是特殊点，因为 f ( x h k ) ≠ f ( x q p ) 。

当 f ( x h k ) = − f ( x q p ) ，此时 x h k x q p 可能是 x n k k x n p p ， x 1 k x n p − 1 p 和 x n k − 1 k x 1 p 。如果 x h k x q p = x n k k x n p p ，根据特殊染色f，不妨令 f ( x h k ) = 2 ， f ( x q p ) = − 2 。此时，用颜色3对点 x h k 和 x q p 重新染色，用颜色2对 ( x h k , x h k x q p ) 染色，用颜色−2对 ( x q p , x h k x q p ) 染色。当 x h k x q p = x 1 k x n p − 1 p 或者 x h k x q p = x n k − 1 k x 1 p ，这两种情况类似，我们介绍 x h k x q p = x 1 k x n p − 1 p 时的情况，根据特殊染色f，我们有 f ( x h k ) = 1 ， f ( x q p ) = − 1 。此时，用颜色3对点 x h k 和 x q p 重新染色，用颜色1对 ( x h k , x h k x q p ) 染色，用颜色−1对 ( x q p , x h k x q p ) 染色。

当 f ( x h k ) ≠ − f ( x q p ) ，又 f ( x h k ) ≠ f ( x q p ) ，因此 x h k x q p = x n k k x n p − 1 p , x n k k x 1 p , x n p p x n k − 1 k 或者 x n k k x 1 p ，上述情况均类似，我们介绍 x h k x q p = x n k k x 1 p 时的情况，根据特殊染色f，不妨令 f ( x h k ) = 2 ， f ( x q p ) = 1 。

如果 x n k k x 1 k 是负边， f ( x 1 k , x n k k x 1 k ) = − 1 ， f ( x n k k , x n k k x 1 k ) = 1 ，用颜色3对 x q p 重新染色，用颜色1对 ( x q p , x h k x q p ) 染色，用颜色−1对 ( x h k , x h k x q p ) 染色。如果 x n k k x 1 k 是正边，则 f ( x 1 k , x n k k x 1 k ) = − 1 ， f ( x n k k , x n k k x 1 k ) = − 1 ，用颜色3对点 x q p ，incidence ( x h k , x h k x 1 k ) 和 ( x 1 k , x h k x 1 k ) 重新染色，用颜色1对 ( x q p , x h k x q p ) 染色，用颜色−1对 ( x h k , x h k x q p ) 染色，该引理得证。

和图的点染色及边染色类似，在对符号图进行全染色时，我们也只需考虑连通图即可。此时，便可以根据引理2.1，引理2.2和引理2.4得出：对任意的最大度为3的符号图 Γ = ( G , σ ) ， χ T ( Γ ) ≤ 5 ，因此定理1得证。而在本文中，我们考虑的是最大度为3的符号图，对其他符号图的全染色问题未曾涉及，类比全染色猜想(TTC)，我们可以提出下述问题：

问题1：对任意的符号图 Γ = ( G , σ ) ， χ T ( Γ ) ≤ Δ + 2 ？

参考文献

[1] Behzad, M. (1965) Graphs and Their Chromatic Numbers. Ph.D. Thesis, Michigan State University, Michigan.
[2] Vijayaditya, N. (1971) On Total Chromatic Number of a Graph. Journal of the London Mathematical Society, s2-3, 405-408.
https://doi.org/10.1112/jlms/s2-3.3.405
[3] Kostochka, A.V. (1996) The Total Chromatic Number of Any Multigraph with Maximum Degree Five Is at Most Seven. Discrete Mathematics, 162, 199-214.
https://doi.org/10.1016/0012-365X(95)00286-6
[4] Harary, F. (1953) On the Notion of Balance of a Signed Graph. The Michigan Mathematical Journal, 2, 143-146.
https://doi.org/10.1307/mmj/1028989917
[5] Behzad, M., Chartrand, G. and Lesniak-Foster, L. (1979) Graphs and Digraphs, Wadsworth International.

为你推荐