#### 期刊菜单

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

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. 引言

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}$ 时的结果。

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

$\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. 定理及其证明

 [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.