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

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,σ)。……