Advances in Applied Mathematics
Vol.
09
No.
10
(
2020
), Article ID:
38062
,
7
pages
10.12677/AAM.2020.910195
最大度为3的符号图的全染色
王 超
浙江师范大学,数学与计算机科学学院,浙江 金华
收稿日期:2020年9月26日;录用日期:2020年10月8日;发布日期:2020年10月15日
摘要
在图 中,使得相邻和相关联的元素均染不同颜色的染色方法,称为图G的正常全染色。使得G为正常全染色的最少颜色数,称为G的全色数,记为 。在本文中,我们给出全染色在符号图中的定义,并在最大度为3的符号图中证明了全色数的上界为5。
关键词
符号图,全染色,最大度
Total Coloring of Signed Graphs with Maximum Degree 3
Chao Wang
College of Mathematics and Computer Science, Zhejiang Normal University, Jinhua Zhejiang
Received: Sep. 26th, 2020; accepted: Oct. 8th, 2020; published: Oct. 15th, 2020
ABSTRACT
For graph , 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 , 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.
Keywords:Signed Graph, Total Coloring, Maximum Degree
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/
1. 引言
图的染色问题是图论的主要研究问题之一,图的染色一般分为点染色,边染色,全染色和其他特定的染色。本文中提到的图 均为简单图,V(G),E(G),Δ(G)分别表示图G的顶点集合和边集合,简记为V,E,Δ。如果 ,, 表示从图G去掉点x及和点x相关联的边, 则表示从图G中去掉边e。
定义1.1 在图 中,对点和边同时进行染色,并且当相邻和相关联的元素均染不同颜色的染色方法,称为图G的正常全染色,使得图G为正常全染色的最少颜色数,称为图G的全色数,记为 。
当我们对图 进行全染色时,因为要同时考虑点和边,在确定全色数时要比确定色数和边色数更困难。根据上述定义,显然 。Behzad [1] 在1965年提出了著名的全染色猜想(TTC):对任意的图G, 。
在1969年,Vijayaditya [2] 证明了 时全染色猜想成立,之后Vostochka [3] 证明了 时全染色猜想成立。
在本文中,我们给出全染色在符号图中的定义,并在最大度为3的符号图中给出了全色数的上界。符号图是Harary [4] 在1953年提出:一个符号图 是在图G的基础上,对其边集E(G)加上符号 ,G称为 的基础图。在符号图 中,对任意的一条边e,如果 ,则称e是正边;如果 ,则称e是负边。符号颜色 当 ; 当 。我们称 为符号颜色集,在 中颜色±1是两个不同但互为相反的颜色。在图 中一个incidence表示 ,v是e的一个顶点。I(G)表示图 中所有的incidence,此时我们有 。现在我们给出符号图中全染色的定义:
定义1.2 在符号图 中,一个全染色f是用颜色集 中的颜色同时对符号图Γ中的incidence和点进行染色,并且如果f满足下面的三个条件:
(1) 对任意的 ,,, 表示边e的符号;
(2) 对任意的 ,, ;
(3) 对任意的 ,v是e的一个顶点, 。
此时称f为符号图 的正常全染色,使得Γ为正常全染色的最少颜色数,称为Γ的全色数,记为 。如果 或 ,则称在点x上颜色a存在。否则称在点x上缺少颜色a。
此时,我们可以看出当符号图 中所有边都是正边时,定义1.1和1.2相同,所以定义1.1是定义1.2的一个特殊情况。根据定义1.2,我们有对任意的符号图Γ, ,Δ表示图Γ的最大度。在本文中我们给出了最大度为3的符号图中全色数的上界。
定理1 如果 是最大度为3的符号图,则 。
2. 定理1的证明
在证明定理1之前,我们需要一些准备工作,首先考虑符号图 中的圈 ,我们对 做如下特殊的全染色,记为 。
情况1:如果 有偶数条正边,则
情况2:如果 有奇数条正边,则
此时,我们称上述在圈 上的染色方法为特殊染色,根据上述的特殊染色,我们可以得出在最大度为2的符号图Γ中, 。因为当Γ是一条路时,对其点用颜色±1进行染色,其边用±2进行染色。在正边个数为奇数的圈 中,我们称点 , 和点 为特殊点。不难看出,如果 是圈 上的特殊染色,对非特殊点 来说,我们交换点 和incidence 的颜色并根据边 的符号确定 的颜色,交换后 仍然是 的正常全染色。
现在我们根据上述在圈中的特殊全染色 来证明定理1,首先证明下面的相关引理。
引理2.1 符号图 是最大度为3的连通图,如果 不是3-正则的,则 。
证明:对符号图Γ的点数做归纳,因为符号图Γ不是3-正则的,因此Γ有一个点x使得 ,当点数为1,2,3时,该结果显然成立。现在假设图Γ的点数大于3,对符号图 ,根据归纳假设, 有一个正常的5-全染色f,其颜色为 。现在我们将用相同的5个颜色把f扩展为图Γ上的正常全染色,我们分为两个情况讨论:
情况1: 如果 ,,在 中,颜色 中至少有一个颜色在点y上没有使用,设为a,此时用颜色a对incidence 染色并根据边xy的符号对 和点x染色,不妨假设边xy为正边, ,因此我们可用颜色a对 染色,用颜色c对点x染色。
情况2: 如果 ,,根据归纳假设符号图 有正常的5-全染色f,因此点y和点z至少分别缺少两个颜色,我们不妨考虑点y和点z分别缺少两个颜色的情况,此时在符号图Γ中 。
情况2.1:点y和点z缺少的两个颜色相同
情况2.1.1:当缺少的两个颜色为相反颜色时,记为 ,此时用颜色a对incidence 染色,根据边xy的符号对 染色,再用与 相反的颜色对 染色,根据边xz的符号对 染色,例如: ,则 , 当边xz为正边,否则 ,现在考虑点x,因为incidence ,,点y和点z至多使用四个不同的颜色,再根据边xy和xz的符号即可对点x进行染色。
情况2.1.2:当缺少的两个颜色不相反时,记为 ,此时分别用颜色a和b对incidence 和 染色,根据边xy和xz的符号对 , 染色,对于点x,可采用情况2.1.1中对点x的方法染色。
情况2.2:点y和点z缺少两个颜色至多一个相同,记为a,此时我们可以在点y和点z缺少的颜色中找出两个颜色既不相同又不相反的颜色,不妨记为 ,此时分别用颜色-a和b对incidence 和 染色,根据边xy和xz的符号对 , 染色,对于点x,仍旧采用情况2.1.1中对点x的方法染色,该引理得证。
引理2.2 符号图 是连通的3-正则图,如果 包含割边 ,则 。
证明:因为 是符号图Γ的一条割边,则 有两个连通分支 和 ,,,因此 ,根据引理2.1, 和 分别有正常的5-全染色 和 。
情况1:如果 是正边,通过对 和 中的颜色进行排列调整,使得
(1) ;
(2) 在 中与点u相关联的两个incidence的颜色和在 中与点v相关联的两个incidence的颜色相同。
此时,对 上的两个incidence可用第五种颜色染色,现在我们便可以将 和 组合并将其扩展为符号图 上的一个正常的5-全染色f。
情况2:如果 是负边,通过对 和 中的颜色进行排列调整,使得
(1) ;
(2) 在 中与点u相关联的两个incidence的颜色和在 中与点v相关联的两个incidence的颜色相同,并且使用的两个颜色相反。
类似的,对 上的两个incidence可用剩余的两个相反颜色染色,现在便可将 和 组合并将其扩展为 上的一个正常的5-全染色f,该引理得证。
在图 中,对集是没有公共顶点的边集合,当对集M覆盖图G中的所有点时,称M为完美对集或1-因子。
引理2.3 [5] 如果G是没有割边的3-正则图,则G的边集可分解为1-因子和边不交的圈的并集。
在符号图中,我们可以看出引理2.3仍然成立,我们将借助引理2.3来证明下面的引理。
引理2.4 符号图 是连通的3-正则图,如果符号图 不包含割边 ,则 。
证明:根据引理2.3,我们有 可以分解为1-因子F和边不交的圈
首先,我们对圈 中的点做标号: ,同时设计如下算法:
算法1:对任意的两个正边个数为奇数的圈 和 满足
(1)
步骤1:如果 中没有正边数为奇数的圈,对每一个圈 的点标号 ,如果 含有正边数为奇数的圈 我们标记 中的一个顶点为 。
步骤2:如果 与正边个数为奇数的未标号圈的顶点相邻,我们进行步骤3,如果 不相邻正边个数为奇数的未标号圈的顶点,我们在以点 起点的两个方向中选择任意一个方向对圈 中的其他点进行标号。此时,如果 与正边个数为奇数的未标号圈的顶点相邻,我们进行步骤4,否则,我们回到步骤1,对未标号的圈继续做顶点标号。
步骤3:如果 与正边个数为奇数的未标号圈的顶点相邻,并将这个圈重新编号为 ,在 中与点 相邻的点记为 并在以点 起点的两个方向中任选一个方向对 中的其他点进行标号,此时我们回到步骤2考虑点 。
步骤4:如果 不相邻正边个数为奇数的未标号圈的顶点但是 与正边个数为奇数的未标号圈的顶点相邻,记为y,我们将这个圈重新编号为 并将y标号为 ,再以点 起点的两个方向中选择任意一个方向对圈 中的其他点进行标号,此时,我们回到步骤2考虑点 。
步骤5:因为图Γ是有限的,该算法最终会结束。我们从一个正边个数为奇数的未标号圈开始,重复步骤2的整个过程,我们可以对所有的正边个数为奇数的圈中的点完成标号,对正边个数为偶数的圈中的点我们可以对其选择任意标号。
现在我们根据对每一个圈 中点的标号 和算法1的结果对符号图Γ做全染色。在符号图Γ中,圈 是Γ上的所有圈,令f是圈 的特殊染色,使用的颜色为 ,现在我们将f扩展为符号图Γ上5-全染色,其颜色集扩充为 。任取 。
情况1: 是正边。
情况1.1:如果 ,用颜色3对 和 进行染色。
情况1.2:如果 。
情况1.2.1:如果点 和 中有一个点不是特殊点,不妨设为 。此时用颜色3对 和 染色并交换点 和incidence 的颜色,再根据边 的符号确定 的颜色。
情况1.2.2:如果点 和 都是特殊点,根据算法1, 可能是 , 和 。当 ,根据特殊染色f,不妨令 ,此时我们有边 和边 有相同的符号,否则的话会与 矛盾。如果边 和 边都是正边,f是特殊染色,因此 和 的颜色都是−1。现在我们用颜色3对点 重新染色并用颜色1对 和 染色。如果边 和 边都是负边,可做类似处理。此时, ,,用颜色3对点 重新染色并用颜色−1对 和 染色,该情况得证。
当 或者 ,这两种情况类似,我们介绍 时的情况,根据特殊染色f, 并且边 和边 有相反的符号,令 是正边, 是负边。因此 ,,,,。下面考虑边 的符号:
如果 是正边,则 ,,此时交换点 和incidence 得到染色 。因为 不是特殊点, 是正常的全染色, ,。现在 的基础上再次交换点 和incidence 的颜色得到染色 ,则 ,,现在用颜色3对 和 进行染色,该情况得证。如果 是负边,用上述方法做类似处理。
情况2: 是负边。
情况2.1:如果 。
情况2.1.1:如果点 和 中有一个点不是特殊点,不妨设为 。根据特殊染色f,不妨令 ,用颜色3对点 重新染色,用颜色1对 染色,用颜色−1对 染色。
情况2.1.2:如果点 和 中都是特殊点,根据算法1, 可能是 , 和 。当 ,不妨令 ,同样的,边 和边 有相同的符号,如果边 和边 都为正边,则边 和边 上incidence的颜色都是−1。用颜色3对 和 染色,用颜色1对 染色,用颜色−1对 染色。如果边 和边 都是负边时,考虑边 和边 ,如果二者有一个是正边,不妨设为 ,此时用颜色3对 , 和 重新染色,用颜色2对 染色,用颜色−2对 染色。如果边 和边 都是负边,用颜色3对 和 重新染色,f是特殊染色并且 是负边,则 ,用颜色1对 重新染色,用颜色−1对 重新染色,此时我们可以用颜色2对 染色,用颜色−2对 染色,得证。
当 或者 ,这两种情况类似,我们介绍 时的情况,根据特殊染色f, ,此时用颜色3对点 重新染色,用颜色1对 染色,因为边 是负边,用颜色−1对 染色。
情况2.2: 。
情况2.2.1:如果点 和 中有一个点不是特殊点,不妨设为 。用颜色3对点 和 重新染色,当 时用颜色 对 染色,此时,根据边 的符号,对其上的另一个incidence 用颜色1或−1染色,而 不是特殊点,和它相关联的两个incidence的颜色为±2,因此该情况得证。当 时,用颜色 对 染色,根据边 的符号对 染色,该情况得证。
情况2.2.2:如果点 和 中都是特殊点,因为 。
当 ,此时 可能是 , 和 。如果 ,根据特殊染色f,不妨令 ,。此时,用颜色3对点 和 重新染色,用颜色2对 染色,用颜色−2对 染色。当 或者 ,这两种情况类似,我们介绍 时的情况,根据特殊染色f,我们有 ,。此时,用颜色3对点 和 重新染色,用颜色1对 染色,用颜色−1对 染色。
当 ,又 ,因此 或者 ,上述情况均类似,我们介绍 时的情况,根据特殊染色f,不妨令 ,。
如果 是负边, ,,用颜色3对 重新染色,用颜色1对 染色,用颜色−1对 染色。如果 是正边,则 ,,用颜色3对点 ,incidence 和 重新染色,用颜色1对 染色,用颜色−1对 染色,该引理得证。
和图的点染色及边染色类似,在对符号图进行全染色时,我们也只需考虑连通图即可。此时,便可以根据引理2.1,引理2.2和引理2.4得出:对任意的最大度为3的符号图 ,,因此定理1得证。而在本文中,我们考虑的是最大度为3的符号图,对其他符号图的全染色问题未曾涉及,类比全染色猜想(TTC),我们可以提出下述问题:
问题1:对任意的符号图 , ?
文章引用
王 超. 最大度为3的符号图的全染色
Total Coloring of Signed Graphs with Maximum Degree 3[J]. 应用数学进展, 2020, 09(10): 1686-1692. https://doi.org/10.12677/AAM.2020.910195
参考文献
- 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.