不含特殊子式的符号图的选择数

宫 辰，武丽芳，刘维婵，张 欣

GONG Chen,WU Lifang,LIU Weichan,ZHANG Xin

西安电子科技大学 数学与统计学院，西安 710071

School of Mathematics and Statistics,Xidian University,Xi’an 710071,China

1 引言

设G是一个有限的、无向的简单图。分别用V(G)与E(G)代表图G的点集合与边集合。对于图G的每条边e，定义其符号σ(e)为 +1或者-1，由此得到的图称为符号图，记为(G,σ)。对于符号图(G,σ)中的边e，如果σ(e)=+1，则称其为正边；如果σ(e)=-1，则称其为负边。符号图的概念最初是由Harary[1]于1955年在一篇数学文章中提出的，之后又被Cartwright与Harary[2]用于社会心理学的研究。例如，在人际关系网中用点代表自然人，如果两个人之间是朋友关系，则将对应这两个人的点用一条正边连接；反之，如果两个人之间是敌对关系，则将对应这两个人的点用一条负边连接。继而，可以通过建立符号图的数学模型来分析人际关系网中的一系列问题，如稳定性、社团划分问题等。

事实上，网络的社团划分问题的研究可以归结于图的染色问题[3-4]。1982年，Zaslavsky[5-7]首次定义了符号图的染色。设(G,σ)是一个符号图，c是从点集V(G)到数集{-k,-(k-1),…,-1,0,1,…,(k-1),k}的映射，其对于图G的任何一条边uv满足：

（1）若σ(uv)=+1，则c(u)≠c(v)；

（2）若σ(uv)=-1，则c(u)≠-c(v)。

该映射c称为图(G,σ)的具有k个颜色的或者具有2k+1个符号颜色的符号点染色。

2016 年 ，Máčajová、Raspaud 与 Škoviera[8]指 出Zaslavsky的上述定义存在缺陷，即该定义不能直接从无符号图的定义直接转换过来。为了克服这个缺陷，Máčajová等结合Zaslavsky的定义，重新给出了符号图的符号点染色的定义。

设Mn为整数集的一个子集，当n=2k时，令Mn={±1,±2,…,±k}；当n=2k+1 时 ，令Mn={0,±1,±2,…,±k}。如果一个从点集V(G)到数集Mn的映射c对于图G的任何一条边uv满足c(u)≠σ(uv)c(v)，则称映射c为符号图(G,σ)的符号n-点染色。使得符号图(G,σ)具有符号n-点染色的最小整数n，称为符号图(G,σ)的符号点色数，记为χ(G,σ)。

2016年，Jin、Kang与Steffen[9]提出了符号图的列表染色的概念。设(G,σ)是一个符号图，对于其每个点v赋予一个颜色列表L(v)⊆ℤ。符号图(G,σ)的L-点染色是其一个点染色c，其满足：

（1）对于任何点v∈V(G)，都有c(v)∈L(v)；

（2）对于任何边uv∈E(G)，都有c(u)≠σ(uv)c(v)。

如果符号图(G,σ)具有L-点染色，则称其为L-点染色。如果符号图(G,σ)上的颜色列表L对于任何点v∈V(G)都有| |L(v)=k，则称该列表L为k-列表。如果对于任何一个k-列表L，符号图(G,σ)都具有L-点染色，则称其是k-点可选的。使得符号图(G,σ)是k-点可选的最小整数k称为符号图(G,σ)的选择数，记为ch(G,σ)。显然有ch(G,σ)≥χ(G,σ)。Jin、Kang与Steffen[9]等研究了符号平面图的列表染色问题，证明了ch(G,σ)≤5对于任何符号平面图(G,σ)成立。

设G是一个图，如果可以通过删除图G的某些点与边或者收缩图G的某些边得到图H，则称图H是图G的一个子式。著名的Wagner定理[10]指出：如果一个图是平面图当且仅当K5与K3,3都不是它的子式。因此，不含K5-子式的图与不含K3,3-子式的图均包含平面图。

本文证明了ch(G,σ)≤5对于任何符号图(G,σ)成立，其中图G不含有K5-子式或K3,3-子式。因此，该结论推广了上述提及的Jin、Kang与Steffen等人的相应结论。

2 几类符号图的列表点染色

2.1 相关定义与术语

设G是一个平面图，C是图G的一个圈。如果圈C关联k个顶点，则称其为k-圈。如果平面图G中的一个圈C的内部和外部都包含图G的顶点，则称圈C是分离的。如果平面图G的除了无界面的所有面的边界都是3-圈，则称G是一个近似三角剖分（注意此时无界面的边界亦有可能是3-圈）。如果平面图G的所有面的边界都是3-圈，称G是一个三角剖分。显然，三角剖分一定是近似三角剖分。

设G1与G2为两个图，则图G1∩G2的点集为V(G1)∩V(G2),边集为E(G1)∩E(G2),图G1∪G2的点集为V(G1)∪V(G2)，边集为E(G1)∪E(G2)。

设G是一个不含K5-子式的图，或不含K3,3-子式的图，或平面图。如果在图G中任意添加一条边所得到的图含有K5-子式，或含有K3,3-子式，或是非平面图，则称图G是边极大的。

设φ是图G的一个染色，图H是图G的一个子图，则φ|H指的是图H的一个染色，使得对于图H的任何一个点v都有φ|H(v)=φ(v)，亦即φ|H是将染色φ限制在图H上的一个染色。

2.2 延拓引理

本节将引入几个重要的引理，用于下一节的主要定理的证明。

引理1[9]设(G,σ)是一个符号图，其中G是一个近似三角剖分。记圈C=[v1,v2,…,vp]为G的无界面的边界。如果L是(G,σ)上的一个颜色列表，其满足L(v1)=α,L(v2)=β,α≠βσ(v1v2)，并且对于任何v∈V(C){v1,v2}有|L(v)|≥3，对于任何v∈V(G)V(C)有|L(v)|≥5，则符号图(G,σ)具有L-点染色。

引理2设(G,σ)是一个符号图，其中G是一个近似三角剖分。设L是(G,σ)上的一个颜色列表，其对于v∈V(G)有| |L(v)≥5。如果H是G的一个同构于K3的子图，且λ是(H,σ)的L-点染色，则λ可以延拓为符号图(G,σ)的L-点染色。

证明 记符号图(H,σ)的3个顶点分别为u、v、w。由于H同构于K3，故它为图G的一个3-圈。下面根据H是否为G的分离的3-圈分两种情况讨论。

情况1H不是G的分离3-圈。

由于G是一个近似三角剖分，故不妨假设H是G的最外面的3-圈，即H关联着G的无界面。此时，在图G中适当地添加边（边上的符号可任意给定）使得其成为一个三角剖分，仍记当前的符号图为(G,σ)。

令G′=G-w。定义符号图(G′,σ)上的列表L′如下：如果x是w在G中的异于u与v的邻点，则令L′(x)=L(x){λ(w)σ(wx)}，否则令L′(x)=L(x)。记u,w1,w2,…,wt,v是w在G中所有邻点，且按该顺序依次排列在w的周围。由于G是一个三角剖分，故G′是一个近似三角剖分，其无界面的边界为圈C=[u,w1,w2,…,wt,v]。由于对于任何x∈V(C){u,v}有|L′(x)| ≥|L(x)|-1≥4，对于任何x∈V(G′)V(C)有|L′(x)|=|L(x)|≥5 ，故根据引理1可知：符号图(G′,σ)具有L′-点染色φ，使得φ(u)=λ(u)且φ(v)=λ(v)。注意到φ(wi)≠λ(w)σ(wwi)对于所有的i∈{1,2,…,t}成立。故将φ与λ组合起来即得到符号图(G,σ)的L-点染色，其中u、v、w的颜色分别为λ(u)、λ(v)、λ(w)。

情况2H是G的分离3-圈。

设(G1,σ)是所有点和边都在H上或其内部的符号图，(G2,σ)是所有点和边都在H上或其外部的符号图。显然，G1与G2都是近似三角剖分且H不是G1的分离3-圈，也不是G2的分离3-圈。

将情况1的讨论分别应用于符号图(G1,σ)与(G2,σ)，可以得到 (G1,σ)的L-点染色φ1与 (G2,σ)的L-点染色φ2，使得φ1(u)=φ2(u)=λ(u)，φ1(v)=φ2(v)=λ(v)且φ1(w)=φ2(w)=λ(w)。因此，将φ1与φ2组合起来即得到符号图(G,σ)的L-点染色，其中u、v、w的颜色分别为λ(u)、λ(v)、λ(w)。

引理3设(G,σ)是一个符号图，其中G是Wagner图（如图1所示）。设L是(G,σ)上的一个颜色列表，其对于v∈V(G)有| |L(v)≥5。如果H是G的一个同构于K2的子图，且λ是(H,σ)的L-点染色，则λ可以延拓为符号图(G,σ)的L-点染色。

图1 Wagner图

证明 由Wagner图的结构对称性，下面仅需考虑两种情况。

情况1H=v1v2。

此时，v1与v2上的颜色分别为λ(v1)与λ(v2)，且λ(v1)≠λ(v2)σ(v1v2)。接下来对图中剩余的点按如下顺序染色，即分别取：

λ(v3)∈L(v3){λ(v2)σ(v2v3)}

λ(v4)∈L(v4){λ(v3)σ(v3v4)}

λ(v5)∈L(v5){λ(v1)σ(v1v5),λ(v4)σ(v4v5)}

λ(v6)∈L(v6){λ(v2)σ(v2v6),λ(v5)σ(v5v6)}

λ(v7)∈L(v7){λ(v3)σ(v3v6),λ(v6)σ(v6v7)}

λ(v8)∈L(v8){λ(v1)σ(v1v8),λ(v4)σ(v4v8),λ(v7)σ(v7v8)}为点v3、v4、v5、v6、v7、v8上的颜色。从而λ已延拓为符号图(G,σ)的L-点染色。

情况2H=v1v5。

此时，v1与v5上的颜色分别为λ(v1)与λ(v5)，且λ(v1)≠λ(v5)σ(v1v2)。接下来对图中剩余的点按如下顺序染色，即分别取：

λ(v2)∈L(v2){λ(v1)σ(v1v2)}

λ(v3)∈L(v3){λ(v2)σ(v2v3)}

λ(v4)∈L(v4){λ(v3)σ(v3v4),λ(v5)σ(v4v5)}

λ(v6)∈L(v6){λ(v2)σ(v2v6),λ(v5)σ(v5v6)}

λ(v7)∈L(v7){λ(v3)σ(v3v6),λ(v6)σ(v6v7)}

λ(v8)∈L(v8){λ(v1)σ(v1v8),λ(v4)σ(v4v8),λ(v7)σ(v7v8)}为点v2、v3、v4、v6、v7、v8上的颜色。从而λ已延拓为符号图(G,σ)的L-点染色。

引理4设(G,σ)是一个符号图，其中G是完全图K5。设L是(G,σ)上的一个颜色列表，其对于v∈V(G)有| |L(v)≥5。如果H是G的一个同构于K2的子图，且λ是(H,σ)的L-点染色，则λ可以延拓为符号图 (G,σ)的L-点染色。

证明 记G的顶点分别为v1、v2、v3、v4与v5。由完全图K5的结构对称性，不妨设H=v1v2。

此时，v1与v2上的颜色分别为λ(v1)与λ(v2)，且λ(v1)≠λ(v2)σ(v1v2)。接下来对图中剩余的点按如下顺序染色，即分别取：

为点v3、v4、v5上的颜色。从而λ已延拓为符号图(G,σ)的L-点染色。

2.3 列表点染色

本节将证明ch(G,σ)≤5对于任何不含K5-子式或K3,3-子式的符号图(G,σ)成立。首先，下列两个引理分别刻画了不含K5-子式的图与不含K3,3-子式的图的结构。

引理5[11]如果图G是边极大的不含K5-子式的图，则G=G1∪G2，其中G1是边极大的不含K5-子式的图，G2是边极大的平面图或者Wagner图，并且G1∩G2=K2或K3。

引理6[11]如果图G是边极大的不含K3,3-子式的图，则G=G1∪G2，其中G1是边极大的不含K3,3-子式的图，G2是边极大的平面图或者完全图K5，并且G1∩G2=K2。

将上述两个引理与第2.2节的延拓定理结合起来，可证明本文的两个主要定理。

定理1如果(G,σ)是一个符号图，其中G是不含K5-子式的图。若L是(G,σ)上的一个颜色列表，其对于v∈V(G)有|L()v|≥5 ，则符号图 (G,σ)具有L-点染色，即有ch(G,σ)≤5。

证明 在图G中适当地添加边使得其成为一个边极大的不含K5-子式的图。对于新添加的每条边，其符号均设定为正。仍记目前得到的符号图为(G,σ)。下面对图G的顶点数进行数学归纳，证明定理1所述结论对于边极大的不含K5-子式的符号图(G,σ)成立，从而定理1得证。

由引理5可知，G=G1∪G2，其中G1是边极大的不含K5-子式的图，G2是边极大的平面图或者Wagner图，并且H≔G1∩G2=K2或K3。由归纳假设，符号图(G1,σ)具有L-点染色φ1。在执行完染色φ1后，图H的所有顶点均已经染好。

此时若H=K2，则当G2是边极大的平面图（即三角剖分）时，由引理1可知，φ1|H可延拓为符号图(G2,σ)的L-点染色φ2；当G2是Wagner图时，由引理3可知，φ1|H亦可延拓为符号图(G2,σ)的L-点染色φ2。无论上述何种情况，将L-点染色φ1与φ2组合起来即得到符号图(G,σ)的L-点染色。

另一方面，若H=K3，则G2不是Wagner图（因Wagner图中不含有三角形），从而G2是边极大的平面图，即三角剖分。由引理2可知，φ1|H可延拓为符号图(G2,σ)的L-点染色φ2，然后将L-点染色φ1与φ2组合起来即得符号图(G,σ)的L-点染色。

定理2如果(G,σ)是一个符号图，其中G是不含K3,3-子式的图。若L是(G,σ)上的一个颜色列表，其对于v∈V(G)有| |L(v)≥5，则符号图(G,σ)具有L-点染色，即有ch(G,σ)≤5。

证明 在图G中适当地添加边使得其成为一个边极大的不含K3,3-子式的图。对于新添加的每条边，其符号均设定为正。仍记目前得到的符号图为(G,σ)。下面对图G的顶点数进行数学归纳，证明定理2所述结论对于边极大的不含K3,3-子式的符号图(G,σ)成立，从而定理2得证。

由引理6可知，G=G1∪G2，其中G1是边极大的不含K5-子式的图，G2是边极大的平面图或者完全图K5，并且H≔G1∩G2=K2。由归纳假设，符号图(G1,σ)具有L-点染色φ1。在执行完染色φ1后，图H的所有顶点均已经染好。

此时当G2是边极大的平面图（即三角剖分）时，由引理1可知，φ1|H可延拓为符号图(G2,σ)的L-点染色φ2；当G2是完全图K5时，由引理4可知，φ1|H亦可延拓为符号图(G2,σ)的L-点染色φ2。无论上述何种情况，将L-点染色φ1与φ2组合起来即得到符号图(G,σ)的L-点染色。

3 结论

定理1与定理2指出任何不含K5-子式或K3,3-子式的符号图的选择数至多为5。由于一个图是平面图当且仅当K5与K3,3都不是它的子式（Wagner定理），故上述结论可以推出Jin、Kang与Steffen于2016年发表的如下结论：

推论1任何符号平面图的选择数至多为5。

由于无符号的平面图可以看成是所有边都是正边的符号面图，故可得如下结论：

推论2任何平面图的选择数至多为5。

由于Voigt[12-13]证明了存在选择数恰好为5的平面图，故推论2中的上界5是最优的。由此可推得：定理1与定理2中关于ch(G,σ)的上界5是最优的。

事实上，对于符号图而言，除了研究其点染色与列表点染色之外，还可以研究其点荫度与圆染色等相关的染色问题。感兴趣的读者可参考文献[14-15]。