相邻顶点度和至多为8的二部图的强边染色
Strong Edge Colorings on Bipartite Graphs with Degree Sum of Adjacent Vertices at Most 8
DOI: 10.12677/AAM.2019.87141, PDF, HTML, XML, 下载: 1,129  浏览: 2,975 
作者: 闫训祥:山东师范大学数学与统计学院,山东 济南
关键词: 二部图强边染色度和Bipartite Graph Strong Edge Coloring Degree Sum
摘要: 二部图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.
文章引用:闫训祥. 相邻顶点度和至多为8的二部图的强边染色[J]. 应用数学进展, 2019, 8(7): 1224-1227. https://doi.org/10.12677/AAM.2019.87141

1. 引言

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

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

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

1) 若 Δ 为偶数,则 χ s ( G ) 5 / 4 Δ 2

2) 若 Δ 为奇数,则 χ s ( G ) 1 / 4 ( 5 Δ 2 2 Δ + 1 )

Δ 2 ,猜想显然成立。Andersen [2] 和Horȧk [3] 证明了当 Δ 3 时猜想成立。

2018年 Huang等人 [4] 给出了 Δ = 4 时的结果。

定理1 (Huang, Santana, Yu, 2018)。若图G的最大度为 Δ = 4 ,则 χ s ( G ) 21

Bruhn和Joos [5] 证明了当 Δ 充分大时, χ s ( G ) 1 .93 Δ 2

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

猜想2 (Brualdi, Massey, 1993)。图G是一个 ( d A , d B ) 二部图,则 χ s ( G ) d A d B

( d A , d B ) 二部图是两部分顶点集A和B满足 Δ ( A ) d A Δ ( B ) d B 的二部图。2008年Nakprasit [7] 证明了:如果图G是一个 4 - - 二部图,则 χ s ( G ) 2 Δ 。2017年Huang等人 [8] 直接使用分解的方法证明了 ( 3 , Δ ) 二部图的结果。

定理2 (Huang, Yu, Zhou, 2017)。如果图G是一个 ( 3 , Δ ) 二部图,则 χ s ( G ) 3 Δ

另外,二部图的强边染色在度和条件限制下得到一些相关结果。2013年Luzar等人 [9] 证明了:若图G是一个二部图,对每条边 u v E ( G ) d ( v ) + d ( u ) 5 ,则 χ s ( G ) 6 。后来,Chen等人 [10] 证明了:(1)对于图G,如果每条边 u v E ( G ) ,都有 d ( v ) + d ( u ) 6 ,则 χ s ( G ) 10 。(2)对于图G,如果每条边 u v E ( G ) ,都有 d ( v ) + d ( u ) 7 ,则 χ s ( G ) 15

2. 定理及其证明

为了方便,令 L = { 1 , 2 , , 22 } 是一个颜色集,用 σ 表示图G的用L中22色的一个强边色数, C σ ( e ) 表示在染色 σ 下分配给 N 2 ( e ) 的颜色集, A σ ( e ) = L \ C σ ( e ) 表示在染色 σ 下边e可利用的颜色集。 ( | C σ ( e 1 ) | , | C σ ( e 2 ) | ) 表示至多分配给 N 2 ( e 1 ) , N 2 ( e 2 ) 的颜色数。 ( | A σ ( e 1 ) | , | A σ ( e 2 ) | ) 表示边 e 1 , e 2 至少可利用的颜色数。下面是本文的结果。

定理3 图G是一个二部图,如果每条边 u v E ( G ) ,都有 d ( v ) + d ( u ) 8 ,则 χ s ( G ) 22

证明:用反证法。设二部图G是一个边数极小的反例,则对每条边 u v E ( G ) ,都有 d ( v ) + d ( u ) 8 ,并且 χ s ( G ) > 22 。显然图G是连通的且对图G的任何真子图 G 是22色强边可染的,接下来我们讨论图G的结构。

断言1:G不含1度点。

否则,假设存在顶点v满足 d ( v ) = 1 N ( v ) = { u } ,满足 d ( u ) 7 。由图G的极小性知, G = G v 有一个22色强边染色 σ 。现在 | C σ ( u v ) | 12 ,因此 | A σ ( u v ) | 10 ,所以我们可以根据贪婪染色把边uv染好,扩展得到图G的一个22色强边染色,矛盾。

断言2:G不含2度点。

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

由以上两个断言可知, δ ( G ) 3 。由相邻两点度和不超过8,可知G不含6,7度点。

断言3:G不含邻接 4 - - 点的3点。

否则,假设存在顶点v满足 d ( v ) = 3 N ( v ) = { v 1 , v 2 , v 3 } ,且 v 1 是一个 4 - - 点。由图G的极小性知, G = G v 有一个22色强边染色 σ 。容易计算得 ( | C σ ( v v 1 ) | , | C σ ( v v 2 ) | , | C σ ( v v 3 ) | ) ( 20 , 19 , 19 ) ,因此 ( | A σ ( v v 1 ) | , | A σ ( v v 2 ) | , | A σ ( v v 3 ) | ) ( 2 , 3 , 3 ) 。所以我们根据贪婪染色依次把边 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是成立的。

致谢

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

参考文献

[1] Erdös, P. (1988) Problems and Results in Combinatorial Analysis and Graph Theory. Annals of Discrete Mathematics, 38, 81-92.
https://doi.org/10.1016/S0167-5060(08)70773-8
[2] Andersen, I.D. (1992) The Strong Chromatic Index of a Cubic Graph Is at Most 10. Discrete Mathematics, 108, 231-252.
https://doi.org/10.1016/0012-365X(92)90678-9
[3] Horák, P., Qing, H. and Trotter, W.T. (1993) Induced Matchings in Cubic Graphs. Journal of Graph Theory, 17, 151-160.
https://doi.org/10.1002/jgt.3190170204
[4] Huang, M., Santana, M. and Yu, G. (2018) Strong Chromatic Index of Graphs with Maximum Degree Four. The Electronic Journal of Combinatorics, 25, Article No. P3.31.
[5] Bruhn, H. and Joos, F. (2015) A Stronger Bound for the Strong Chromatic Index. Electronic Notes in Discrete Mathematics, 49, 277-284.
https://doi.org/10.1016/j.endm.2015.06.038
[6] Brualdi, A.T. and Quinn Massey, J.J. (1993) Incidence and Strong Edge-Colorings of Graphs. Discrete Mathematics, 122, 51-58.
https://doi.org/10.1016/0012-365X(93)90286-3
[7] Nakprasit, K. (2008) A Note on the Strong Chromatic Index of Bipartite Graphs. Discrete Mathematics, 308, 3726-3728.
https://doi.org/10.1016/j.disc.2007.07.034
[8] Huang, M., Yu, G. and Zhou, X. (2017) The Strong Chromatic Index of (3, ∆)-Bipartite Graphs. Discrete Mathematics, 340, 1143-1149.
https://doi.org/10.1016/j.disc.2016.10.016
[9] Lužar, B., Mockovčiaková, M., Soták, R. and Škrekovski, R. (2013) Strong Edge Coloring of Subcubic Bipartite Graphs. ArXiv: 1311.6668v2.
https://arxiv.org/abs/1311.6668
[10] Chen, L., Huang, M., Yu, G. and Zhou, X. (2018) The Strong Edge-Coloring for Graph with Small Edge Weight.