Advances in Applied Mathematics
Vol.
08
No.
07
(
2019
), Article ID:
31370
,
4
pages
10.12677/AAM.2019.87141
Strong Edge Colorings on Bipartite Graphs with Degree Sum of Adjacent Vertices at Most 8
Xunxiang Yan
School of Mathematics and Statistics, Shandong Normal University, Jinan Shandong
Received: Jun. 28th, 2019; accepted: Jul. 16th, 2019; published: Jul. 23rd, 2019
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.
Keywords:Bipartite Graph, Strong Edge Coloring, Degree Sum
相邻顶点度和至多为8的二部图的强边染色
闫训祥
山东师范大学数学与统计学院,山东 济南
收稿日期:2019年6月28日;录用日期:2019年7月16日;发布日期:2019年7月23日
摘 要
二部图G指顶点集V(G)可以划分成两个不相交的子集,使得在同一个子集内的顶点不相邻的图。图G的强边染色是在正常边染色的基础上,要求长至多为3的路上的边染不同的颜色。我们证明了每一对相邻顶点度和至多为8的二部图有一个强边染色至多22种颜色。
关键词 :二部图,强边染色,度和
Copyright © 2019 by author(s) and Hans Publishers Inc.
This work is licensed under the Creative Commons Attribution International License (CC BY).
http://creativecommons.org/licenses/by/4.0/
1. 引言
本文考虑的都是简单无向图。对于图G,把它的顶点集、边集、最小度和最大度分别记为 , , 和 ,用 和 表示顶点v的度数和邻域,且 。如果顶点v的度数等于k (至少是k或至多是k),则称v是k-点( 点或 点)。顶点v的一个k-邻点指的是 中度数为k的顶点。如果两个顶点与同一条边关联,则称两个顶点是相邻的。对于每条边 , 表示相邻顶点v和u的度数之和,简称度和。如果两条边有一个公共顶点,则称这两条边是距离为1的。如果它们不是距离为1的且存在一条公共边,则称这两条边是距离为2的。 表示与边e距离至多为2的边集。
二部图指顶点集可以划分成两个不相交的子集,使得在同一个子集内的顶点不相邻的图。图G的强边染色是在正常边染色的基础上,要求长至多为3的路上的边染不同的颜色。强边染色所用颜色的最小整数称为图G的强边色数,记为 。1985年,Erdös, Nesetril [1] 提出了强边染色猜想:
猜想1 (Erdös, Nesetril, 1985)。设图G的最大度为 ,则
1) 若 为偶数,则 ;
2) 若 为奇数,则 。
当 ,猜想显然成立。Andersen [2] 和Horȧk [3] 证明了当 时猜想成立。
2018年 Huang等人 [4] 给出了 时的结果。
定理1 (Huang, Santana, Yu, 2018)。若图G的最大度为 ,则 。
Bruhn和Joos [5] 证明了当 充分大时, 。
在本文中,我们研究了二部图的强边染色。1993年Brualdi和Massey [6] 提出了关于二部图的强边染色猜想:
猜想2 (Brualdi, Massey, 1993)。图G是一个 二部图,则 。
二部图是两部分顶点集A和B满足 和 的二部图。2008年Nakprasit [7] 证明了:如果图G是一个 二部图,则 。2017年Huang等人 [8] 直接使用分解的方法证明了 二部图的结果。
定理2 (Huang, Yu, Zhou, 2017)。如果图G是一个 二部图,则 。
另外,二部图的强边染色在度和条件限制下得到一些相关结果。2013年Luzar等人 [9] 证明了:若图G是一个二部图,对每条边 , ,则 。后来,Chen等人 [10] 证明了:(1)对于图G,如果每条边 ,都有 ,则 。(2)对于图G,如果每条边 ,都有 ,则 。
2. 定理及其证明
为了方便,令 是一个颜色集,用 表示图G的用L中22色的一个强边色数, 表示在染色 下分配给 的颜色集, 表示在染色 下边e可利用的颜色集。 表示至多分配给 的颜色数。 表示边 至少可利用的颜色数。下面是本文的结果。
定理3 图G是一个二部图,如果每条边 ,都有 ,则 。
证明:用反证法。设二部图G是一个边数极小的反例,则对每条边 ,都有 ,并且 。显然图G是连通的且对图G的任何真子图 是22色强边可染的,接下来我们讨论图G的结构。
断言1:G不含1度点。
否则,假设存在顶点v满足 , ,满足 。由图G的极小性知, 有一个22色强边染色 。现在 ,因此 ,所以我们可以根据贪婪染色把边uv染好,扩展得到图G的一个22色强边染色,矛盾。
断言2:G不含2度点。
否则,假设存在顶点v满足 , ,满足 和 。由图G的极小性知, 有一个22色强边染色 。现在 ,因此 。所以我们可以根据贪婪染色依次把边uv和wv染好,扩展得到图G的一个22色强边染色,矛盾。
由以上两个断言可知, 。由相邻两点度和不超过8,可知G不含6,7度点。
断言3:G不含邻接 点的3点。
否则,假设存在顶点v满足 , ,且 是一个 点。由图G的极小性知, 有一个22色强边染色 。容易计算得 ,因此 。所以我们根据贪婪染色依次把边 、 和 染好,扩展得到图G的一个22色强边染色,矛盾。
由以上三个断言可知,极小反例如果有3度点,它们的邻点都是5点。由相邻两点度和不超过8,和断言1,2知道,如果有5点,它们的邻点都是3点。又因图G是连通的,这种情况图G只能是两部分最大度分别是5和3的二部图,由定理2,15种颜色足够给出强边染色,矛盾。
综上可知,极小反例只有4度点,即图G是4-正则的二部图,由定理1,21种颜色可以给出它的一个强边染色,矛盾。
因此,极小反例图G不存在,从而定理3是成立的。
致谢
感谢导师张霞副教授给我介绍强边染色的相关问题,并对本文书写进行了全面的修改。最后,向各位尊敬的评审专家致以诚挚的感谢,谢谢你们对本论文做出的评审以及提出的宝贵意见。
文章引用
闫训祥. 相邻顶点度和至多为8的二部图的强边染色
Strong Edge Colorings on Bipartite Graphs with Degree Sum of Adjacent Vertices at Most 8[J]. 应用数学进展, 2019, 08(07): 1224-1227. https://doi.org/10.12677/AAM.2019.87141
参考文献
- 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.