相邻顶点度和至多为8的二部图的强边染色

Strong Edge Colorings on Bipartite Graphs with Degree Sum of Adjacent Vertices at Most 8

摘要: 二部图G指顶点集V(G)可以划分成两个不相交的子集，使得在同一个子集内的顶点不相邻的图。图G的强边染色是在正常边染色的基础上，要求长至多为3的路上的边染不同的颜色。我们证明了每一对相邻顶点度和至多为8的二部图有一个强边染色至多22种颜色。

Abstract: A bipartite graph G is a graph in which V(G) can be partitioned into two disjoint subsets, so that the vertices in the same subset are not adjacent. A strong edge coloring of graph G is an edge coloring in such a way that any two edges on a path of length at most three receive distinct colors. We prove that each bipartite graph with degree sum of each pair of adjacent vertices at most 8 has a strong edge coloring with at most 22 colors.

1. 引言

本文考虑的都是简单无向图。对于图G，把它的顶点集、边集、最小度和最大度分别记为 $V\left(G\right)$ ， $E\left(G\right)$ ， $\delta \left(G\right)$ 和 $\Delta \left(G\right)$ ，用 $d\left(v\right)$ 和 $N\left(v\right)$ 表示顶点v的度数和邻域，且 $d\left(v\right)=\left|N\left(v\right)\right|$ 。如果顶点v的度数等于k (至少是k或至多是k)，则称v是k-点( $k^{+}\text{-}$ 点或 $k^{\text{-}}\text{-}$ 点)。顶点v的一个k-邻点指的是 $N\left(v\right)$ 中度数为k的顶点。如果两个顶点与同一条边关联，则称两个顶点是相邻的。对于每条边 $uv\in E\left(G\right)$ ， $d\left(v\right)+d\left(u\right)$ 表示相邻顶点v和u的度数之和，简称度和。如果两条边有一个公共顶点，则称这两条边是距离为1的。如果它们不是距离为1的且存在一条公共边，则称这两条边是距离为2的。 $N_{\text{2}}\left(e\right)$ 表示与边e距离至多为2的边集。

二部图指顶点集可以划分成两个不相交的子集，使得在同一个子集内的顶点不相邻的图。图G的强边染色是在正常边染色的基础上，要求长至多为3的路上的边染不同的颜色。强边染色所用颜色的最小整数称为图G的强边色数，记为 ${{\chi }^{\prime }}_s\left(G\right)$ 。1985年，Erdös, Nesetril [1] 提出了强边染色猜想：

猜想1 (Erdös, Nesetril, 1985)。设图G的最大度为 $\Delta$ ，则

1) 若 $\Delta$ 为偶数，则 ${{\chi }^{\prime }}_s\left(G\right)\le \text{5}/\text{4}{\Delta }^{\text{2}}$ ；

2) 若 $\Delta$ 为奇数，则 ${{\chi }^{\prime }}_s\left(G\right)\le \text{1}/\text{4}\left(\text{5}{\Delta }^{\text{2}}-\text{2}\Delta +\text{1}\right)$ 。

当 $\Delta \le \text{2}$ ，猜想显然成立。Andersen [2] 和Horȧk [3] 证明了当 $\Delta \le \text{3}$ 时猜想成立。

2018年 Huang等人 [4] 给出了 $\Delta =\text{4}$ 时的结果。

定理1 (Huang, Santana, Yu, 2018)。若图G的最大度为 $\Delta =\text{4}$ ，则 ${{\chi }^{\prime }}_s\left(G\right)\le \text{21}$ 。

Bruhn和Joos [5] 证明了当 $\Delta$ 充分大时， ${{\chi }^{\prime }}_s\left(G\right)\le \text{1}\text{.93}{\Delta }^{\text{2}}$ 。

在本文中，我们研究了二部图的强边染色。1993年Brualdi和Massey [6] 提出了关于二部图的强边染色猜想：

猜想2 (Brualdi, Massey, 1993)。图G是一个 $\left(d_A,d_B\right)-$ 二部图，则 ${{\chi }^{\prime }}_s\left(G\right)\le d_A{d}_B$ 。

$\left(d_A,d_B\right)-$ 二部图是两部分顶点集A和B满足 $\Delta \left(A\right)\le d_A$ 和 $\Delta \left(B\right)\le d_B$ 的二部图。2008年Nakprasit [7] 证明了：如果图G是一个 ${\text{4}}^{\text{-}}\text{-}$ 二部图，则 ${{\chi }^{\prime }}_s\left(G\right)\le \text{2}\Delta$ 。2017年Huang等人 [8] 直接使用分解的方法证明了 $\left(\text{3},\Delta \right)-$ 二部图的结果。

定理2 (Huang, Yu, Zhou, 2017)。如果图G是一个 $\left(\text{3},\Delta \right)-$ 二部图，则 ${{\chi }^{\prime }}_s\left(G\right)\le \text{3}\Delta$ 。

另外，二部图的强边染色在度和条件限制下得到一些相关结果。2013年Luzar等人 [9] 证明了：若图G是一个二部图，对每条边 $uv\in E\left(G\right)$ ， $d\left(v\right)+d\left(u\right)\le \text{5}$ ，则 ${{\chi }^{\prime }}_s\left(G\right)\le \text{6}$ 。后来，Chen等人 [10] 证明了：(1)对于图G，如果每条边 $uv\in E\left(G\right)$ ，都有 $d\left(v\right)+d\left(u\right)\le \text{6}$ ，则 ${{\chi }^{\prime }}_s\left(G\right)\le \text{10}$ 。(2)对于图G，如果每条边 $uv\in E\left(G\right)$ ，都有 $d\left(v\right)+d\left(u\right)\le \text{7}$ ，则 ${{\chi }^{\prime }}_s\left(G\right)\le \text{15}$ 。

2. 定理及其证明

为了方便，令 $L=\left\{1,2,\cdots ,22\right\}$ 是一个颜色集，用 $\sigma$ 表示图G的用L中22色的一个强边色数， $C_{\sigma }\left(e\right)$ 表示在染色 $\sigma$ 下分配给 $N_{\text{2}}\left(e\right)$ 的颜色集， $A_{\sigma }\left(e\right)=L\backslash C_{\sigma }\left(e\right)$ 表示在染色 $\sigma$ 下边e可利用的颜色集。 $\left(\left|C_{\sigma }\left(e_1\right)\right|,\left|C_{\sigma }\left(e_2\right)\right|\right)$ 表示至多分配给 $N_2\left(e_1\right),N_2\left(e_2\right)$ 的颜色数。 $\left(\left|A_{\sigma }\left(e_1\right)\right|,\left|A_{\sigma }\left(e_2\right)\right|\right)$ 表示边 $e_1,e_2$ 至少可利用的颜色数。下面是本文的结果。

定理3 图G是一个二部图，如果每条边 $uv\in E\left(G\right)$ ，都有 $d\left(v\right)+d\left(u\right)\le \text{8}$ ，则 ${{\chi }^{\prime }}_s\left(G\right)\le \text{22}$ 。

证明：用反证法。设二部图G是一个边数极小的反例，则对每条边 $uv\in E\left(G\right)$ ，都有 $d\left(v\right)+d\left(u\right)\le \text{8}$ ，并且 ${{\chi }^{\prime }}_s\left(G\right)>\text{22}$ 。显然图G是连通的且对图G的任何真子图 $G^{\prime }$ 是22色强边可染的，接下来我们讨论图G的结构。

断言1：G不含1度点。

否则，假设存在顶点v满足 $d\left(v\right)=1$ ， $N\left(v\right)=\left\{u\right\}$ ，满足 $d\left(u\right)\le 7$ 。由图G的极小性知， $G^{\prime }=G-v$ 有一个22色强边染色 $\sigma$ 。现在 $\left|C_{\sigma }\left(uv\right)\right|\le 12$ ，因此 $\left|A_{\sigma }\left(uv\right)\right|\ge 10$ ，所以我们可以根据贪婪染色把边uv染好，扩展得到图G的一个22色强边染色，矛盾。

断言2：G不含2度点。

否则，假设存在顶点v满足 $d\left(v\right)=\text{2}$ ， $N\left(v\right)=\left\{u,w\right\}$ ，满足 $d\left(u\right)\le \text{6}$ 和 $d\left(w\right)\le \text{6}$ 。由图G的极小性知， $G^{\prime }=G-v$ 有一个22色强边染色 $\sigma$ 。现在 $\left(\left|C_{\sigma }\left(uv\right)\right|,\left|C_{\sigma }\left(wv\right)\right|\right)\le \left(17,17\right)$ ，因此 $\left(\left|A_{\sigma }\left(uv\right)\right|,\left|A_{\sigma }\left(wv\right)\right|\right)\ge \left(5,5\right)$ 。所以我们可以根据贪婪染色依次把边uv和wv染好，扩展得到图G的一个22色强边染色，矛盾。

由以上两个断言可知， $\delta \left(G\right)\ge \text{3}$ 。由相邻两点度和不超过8，可知G不含6，7度点。

断言3：G不含邻接 ${\text{4}}^{\text{-}}\text{-}$ 点的3点。

否则，假设存在顶点v满足 $d\left(v\right)=\text{3}$ ， $N\left(v\right)=\left\{v_1,v_2,v_3\right\}$ ，且 $v_1$ 是一个 ${\text{4}}^{\text{-}}\text{-}$ 点。由图G的极小性知， $G^{\prime }=G-v$ 有一个22色强边染色 $\sigma$ 。容易计算得 $\left(\left|C_{\sigma }\left(v{v}_1\right)\right|,\left|C_{\sigma }\left(v{v}_2\right)\right|,\left|C_{\sigma }\left(v{v}_3\right)\right|\right)\le \left(20,19,19\right)$ ，因此 $\left(\left|A_{\sigma }\left(v{v}_1\right)\right|,\left|A_{\sigma }\left(v{v}_2\right)\right|,\left|A_{\sigma }\left(v{v}_3\right)\right|\right)\ge \left(2,3,3\right)$ 。所以我们根据贪婪染色依次把边 $v{v}_1$ 、 $v{v}_2$ 和 $v{v}_3$ 染好，扩展得到图G的一个22色强边染色，矛盾。

由以上三个断言可知，极小反例如果有3度点，它们的邻点都是5点。由相邻两点度和不超过8，和断言1，2知道，如果有5点，它们的邻点都是3点。又因图G是连通的，这种情况图G只能是两部分最大度分别是5和3的二部图，由定理2，15种颜色足够给出强边染色，矛盾。

综上可知，极小反例只有4度点，即图G是4-正则的二部图，由定理1，21种颜色可以给出它的一个强边染色，矛盾。

因此，极小反例图G不存在，从而定理3是成立的。

致谢

感谢导师张霞副教授给我介绍强边染色的相关问题，并对本文书写进行了全面的修改。最后，向各位尊敬的评审专家致以诚挚的感谢，谢谢你们对本论文做出的评审以及提出的宝贵意见。