Δ ≥ 4，g ≥ 6的符号图的边染色

Edge Coloring of Signed Graphs with Δ ≥ 4 and g ≥ 6

摘要: 2020年，Behr及Zhang等人将边染色的概念推广到符号图上。令符号图(G, σ)可嵌入非负欧拉特征值的表面，本文通过分析极小反例的结构性质，证明了Δ ≥ 4，g ≥ 6的符号图(G, σ)边色数为Δ。

Abstract: In 2020, Behr and Zhang et al. extended the concept of edge coloring to signed graphs. Let the signed graph (G, σ) be embeddable in a surface with non-negative Euler characteristic. By analyzing the structural properties of the minimal counterexample, this paper proves that the edge chromatic number of the signed graph (G, σ) with Δ ≥ 4 and g ≥ 6 is Δ.

1. 引言

令图(G, σ)可嵌入非负欧拉特征值的表面，如果一个图可以画在一个表面上使得任何两条边之间不产生交叉，上述这种画法称为(G, σ)的表面嵌入。本文考虑的每一个图都是简单的，无向的，有限的并且是非空的。对于图(G, σ)，把它顶点集、边集、面集、最大度、最小度以及围长分别记作V(G)、E(G)、F(G)、Δ(G)、δ(G)和g(G)。图(G, σ)中最短长度的圈称为G的围长。对于图(G, σ)的一个面f，若d(f) = k (或d(f) ≥ k，或d(f) ≤ k)，则称f为一个k-面(或k⁺-面，或k⁻-面)。对于面f，我们用b(f)来表示面f的边界，当面f中的顶点依次为$x_1,x_2,\cdots ,x_k$ 时，我们用$\left[x_1{x}_2\cdots x_k\right]$ 表示面f。

2020年，Behr [1]和Zhang等人[2]分别给出符号图边染色定义。这给研究者提供了新的研究方向，普通图的边染色通常是关注相邻边的颜色不同，而符号图的边染色在此基础上还考虑了边的符号。这种扩展使得问题更加复杂，也适用于更多现实场景，如社交网络中的友好与敌对关系，化学反应中的促进与抑制作用等，所以符号图边染色的研究具有现实意义。本文即研究Δ ≥ 4，g ≥ 6的符号图的边染色，将 Li和Luo [3]的一部分结论推广至符号图中。

对于符号图(G, σ)，将E(G)中的每条边e = uv视为两条半边$h\left(u:e\right)$ 和$h\left(v:e\right)$ ，分别是与u和v关联的半边。令H(G)为(G, σ)中所有半边的集合，H_G(v)为关联顶点v的所有半边的集合。

符号图(G, σ)是带有符号σ的图$G:E\left(G\right)\to \left\{+,-\right\}$ ，G称为(G, σ)的底图。为了方便起见，本文中G实 指(G, σ)，只有在需要时才会指定符号σ。

令k为正整数且

$M_k=\{\begin{array}{ll}\pm 1,\pm 2,\cdots ,\pm n\hfill & k=2n\hfill \\ 0,\pm 1,\pm 2,\cdots ,\pm n\hfill & k=2n+1\hfill \end{array}$

定义1.1 [1]：设映射$\phi :H\left(G,\sigma \right)\to M_k$ ，满足以下两个条件：

(1) 对任意$v\in V\left(G\right)$ ，任意两条半边$h_1,h_2\in H_G\left(v\right)$ ，$h_1\ne h_2$ ；

(2) 对任意$e=uv\in E\left(G\right)$ ，都有$\left(h\left(u:e\right)\right)=-\sigma \left(e\right)\left(h\left(v:e\right)\right)$ 。

则映射φ称为(G, σ)的Mk-边染色，简称k-边染色。若符号图存在k-边染色，则称之为k-边可染的。符号图(G, σ)的边色数用${{\chi }^{\prime }}_{\pm }\left(G,\sigma \right)$ 表示。

在无符号图中存在一个著名的Vizing定理：

定理1.2 [4]：具有最大度Δ的图G正确边着色所需颜色数量是Δ或Δ + 1。

在2003年，Li和Luo [3]根据以上定理以及一些引理证明出关于非平面图的一些结果：

定理1.3 [3]：图G为简单图，最大度为Δ，围长为g，且图G可嵌入表面Σ满足欧拉特征值$\chi \left(\Sigma \right)\ge 0$ ，则在以下每种情况，图G边色数为Δ：

(1) Δ ≥ 5且g ≥ 4；

(2) Δ ≥ 4且g ≥ 5；

(3) Δ ≥ 3且g ≥ 9或Δ ≥ 3且g ≥ 8且$\chi \left(\Sigma \right)=0$ 。

在2020年，Behr [1]证明了符号版本的Vizing定理。

定理1.4 [1] (符号图Vizing定理)：对于一个简单符号图，$\Delta \le {{\chi }^{\prime }}_{\pm }\left(G,\sigma \right)\le \Delta +1$ 。

本文将定理1.3中(2)推广至符号图中，证明以下定理：

定理1.5 若符号图(G, σ)满足Δ ≥ 4且g ≥ 6且可嵌入表面Σ满足欧拉特征值$\chi \left(\Sigma \right)\ge 0$ ，则${{\chi }^{\prime }}_{\pm }\left(G,\sigma \right)=\Delta$ 。

2. 定理1.5的证明

2.1. 极小反例的性质

首先介绍定理证明所必需引理及定理：

2023年，Cao等人[5]证明了关于符号图偶最大度的Vizing邻接引理。

引理2.1 设符号图(G, σ)为具有偶最大度Δ ≥ 2的Δ-临界符号图，若$xy\in E\left(G\right)$ ，则顶点x至少有$\max \left\{2,\Delta -d\left(y\right)+1\right\}$ 个度为Δ的邻点。

从符号图Vizing邻接引理，容易得到以下推论：

推论2.2 令(G, σ)为Δ-临界符号图，则每个顶点邻接至多一个2度点和至少两个Δ度点。

设图(G, σ)可嵌入欧拉特征值为$\chi \left(\Sigma \right)$ 的曲面Σ中，则图(G, σ)的面f的欧拉贡献定义如下：

$\varphi \left(f\right)=1-\frac{d\left(f\right)}{2}+{\displaystyle \sum _{v\in V\left(G\right)}\frac{1}{d\left(v\right)}}$

这里的V(f)表示面f的边界的顶点集。

定理2.3 [6] [7]令图G为连通，无环，无桥图，可嵌入欧拉特征值为$\chi \left(\Sigma \right)$ 的表面Σ中，则

${\displaystyle \sum _{f\in F\left(G\right)}\varphi \left(f\right)}=\chi \left(\Sigma \right)$

若一个面的欧拉贡献为非负(正、零)，则称其为非负(正、零)面。

通过定理2.3中的公式可以计算出最小度至少为3的简单图的正面和零面，如表1和表2所示。由于在证明过程中，只需长度至少为4的非负面的结构，所以只需表1中的正面及表2中的零面。令H是嵌入在欧拉特征值$\chi \left(\Sigma \right)\ge 0$ 的曲面Σ上的图。

本文主要运用反证法，若定理不成立，则存在一个使得定理不成立的极小反例，通过研究极小反例的性质得到矛盾，说明极小反例不存在，从而定理成立。

设G是满足定理1.5的极小反例，其中$\left|E\left(G\right)\right|$ 尽可能小。

Table 1. Positive faces

表1. 正面

dH(f)	边界顶点度序列
4	3，3，3，≤Δ
4	3，3，4，≤11
4	3，3，5，≤7
4	3，4，4，≤5
5	3，3，3，3，≤5

Table 2. Zero faces

表2. 零面

dH(f)	边界顶点度序列
4	3，3，4，12
4	3，3，6，6
4	3，4，4，6
4	4，4，4，4
5	3，3，3，3，6
5	3，3，3，4，4
6	3，3，3，3，3，3

若路径v₀v₁...v_r满足除v₀和v_r外其余点的度数都为2，且d(v₀)，d(v_r) > 2，则路径v₀v₁...v_r被称为长度为r的细分边。v₀和v_r被称为细分边的端点。若两条细分边至少有一个端点相同，则称这两条细分边相邻。

那么，(1) (2) (3)容易得出：

• G为2-连通且δ ≥ 2，Δ ≥ 4。

• 任何细分边的长度至多为2，因为根据推论2.2，每个2-点与两个∆-点相邻。

• 任意两条细分2-边彼此不相邻，因为根据推论2.2，每个顶点至多与一个2-点相邻。

将G中的每条细分2-边替换为单边得到图$\overline{G}$ 。对于每条边$e=xy\in E\left(G\right)$ ，记α(e)为e在G中对应的边。所以α(e)要么是e，要么是端点为x和y的细分2-边。

此时，容易推出(4) (5)：

• $\delta \left(\overline{G}\right)\ge 3$ 且$\overline{G}$ 中任意顶点度数与G中顶点度数相同，即对于每个$v\in V\left(\overline{G}\right)\subseteq V\left(G\right)$ ，有 $d_{\overline{G}}\left(v\right)=d_G\left(v\right)$ 。

• 对于图$\overline{G}$ 中的每条边$e=xy\in E\left(\overline{G}\right)$ ，若x，y为∆度点，则α(e)可能为细分2-边，否则α(e) = e。因为根据推论2.2，任何2度顶点都与两个∆度顶点相邻。

引理2.4 图$\overline{G}$ 的围长至少为4。

证明：反证法，假设$\overline{G}$ 包含一个长度至多为3的圈$\overline{C}$ 。记C为$\overline{C}$ 在G中对应的圈。那么，根据(3)，C的长度至多为4，否则在C上存在两条相邻的细分2-边，这与G的围长至少为6的假设相矛盾。

引理2.5 在图$\overline{G}$ 中，任何度数为3的顶点至多与一个度数为3的顶点相邻。

证明：反证法，假设存在一个3度点x与两个3度点y，z相邻。根据(5)，x，y，z都不为∆度点，所以α(xy) = xy且α(xz) = xz。根据(4)，$\overline{G}$ 中任意顶点度数与G中顶点度数相同，所以x，y，z在G中均为3度点。因此，在G中，3度点与两个3度点相邻。这表明x至多与一个Δ度点相邻，这与推论2.2中x至少与两个Δ度点相邻相矛盾。

引理2.6 对于$\overline{G}$ 中的任意一个4-面$f^{\prime }=\left[x_1{x}_2{x}_3{x}_4\right]$ ，均有$d_{\overline{G}}\left(x_i\right)\ge 4$ ，其中$i=1,2,3,4$ 。

证明：反证法，假设存在x_i，$d_{\overline{G}}\left(x_i\right)\le 3$ 。不妨令$d_{\overline{G}}\left(x_1\right)=3$ ，由(4)可知，$\overline{G}$ 中任意顶点度数与G中顶点度数相同，所以$d_G\left(x_1\right)=3$ 。由(5)可知，由于x₁不为∆度点，所以$\alpha \left(x_1{x}_2\right)=x_1{x}_2$ 且$\alpha \left(x_1{x}_4\right)=x_1{x}_4$ 。由于假设中G的围长至少为6，所以α(x₂x₃)与α(x₃x₄)在G中必为细分2-边，这与(3)中任意两条细分2-边彼此不相邻相矛盾。

引理2.7 $\overline{G}$ 不包含任何正面。因此，$\overline{G}$ 的所有面均为零面。

证明：反证法，假设$\overline{G}$ 包含一个正面$f^{\prime }$ 。根据表1，$f^{\prime }$ 的长度要么为4，要么为5。若$d\left(f^{\prime }\right)=4$ ，根据表1，$f^{\prime }$ 的边界上至少有一个3度点，这与引理2.6相矛盾。若$d\left(f^{\prime }\right)=5$ ，根据表1，在$f^{\prime }$ 的边界上存在一个3度点与两个3度点相邻，这与引理2.5相矛盾。由于$\chi \left(\Sigma \right)\ge 0$ ，所以$\overline{G}$ 的所有面均为零面。

引理2.8 图$\overline{G}$ 中的每个面的长度均为4且与四个4度点相邻。因此，图$\overline{G}$ 是4-正则图，且$\overline{G}$ 中每个面的长度均为4。

证明：设$\overline{f}\in F\left(\overline{G}\right)$ 。那么，根据引理2.7，$\overline{f}$ 是零面。由引理2.5知任何度数为3的顶点至多与一个度数为3的顶点相邻，由引理2.6知$\overline{G}$ 中的任意一个4-面边界顶点度数至少为4，再根据表2，易得$d\left(\overline{f}\right)=4$ 且$\overline{f}$ 边界的每个顶点均为4度点。

2.2. 证明

证明：设$\overline{f_1}=\left[x_1{x}_2{x}_3{x}_4\right]$ 是$\overline{G}$ 的一个4-面。记$f_1\in F\left(G\right)$ 为$\overline{f_1}$ 对应的面。由于G的围长为6，所以存在两条不邻接的边为细分2-边。不失一般性，假设$\alpha \left(x_1{x}_2\right)$ 与$\alpha \left(x_3{x}_4\right)$ 是细分2-边。记$\alpha \left(x_1{x}_2\right)=x_1{y}_1{x}_2$ ，$\alpha \left(x_3{x}_4\right)=x_3{y}_2{x}_4$ ，其中$d_G\left(y_1\right)=d_G\left(y_2\right)=2$ 。设$f_2=\left[x_2{x}_5{x}_6{x}_3\right]$ 是与f₁相邻且共用边x₂x₃的4-面。根据(3)，任意两条细分2-边彼此不相邻，所以$\alpha \left(x_2{x}_5\right)=x_2{x}_5$ 、$\alpha \left(x_2{x}_3\right)=x_2{x}_3$ 以及$\alpha \left(x_3{x}_6\right)=x_3{x}_6$ 。因此，f₂至多为5-面，这与g ≥ 6相矛盾。以上矛盾说明极小反例G不存在，从而定理1.5成立。