A Note on Strong Edge Coloring of Sparse Graphs
A Note on Strong Edge Coloring of Sparse Graphs
复制标题
关于稀疏图强边着色的注解
DOI：
10.1007/s10114-018-7186-7
复制
发表时间：
2019
影响因子：
0.7
通讯作者：
Xu Bao Gang
中科院分区：
文献类型：
--
作者：
Dong Wei;Li Rui;Xu Bao Gang
图的强边着色是指距离不超过2的边得到不同颜色的适当边着色。图的强色指数x ' s(G)是在G的强边着色中使用的最小颜色数。在g的顶点的排序q中，ginq的顶点的后退度是相邻的顶点的个数，每个顶点的索引都小于xinq。设G为最大度Δ和最大为2k的最大平均度的图。[J]。图论，83,334 - 339(2016)]提出了一种算法，该算法生成gin的边排序，其中每条边的后退度最多为4kΔ−2kin G的线形图的平方，这意味着χ ' s(G)≤4kΔ−2k+ 1。在本文中，我们通过引入一个处理局部结构的新过程来改进Yang和Zhu的算法。我们的算法生成了G的边的排序，其中每条边最多有（4k−1）Δ−2kin G的线形图的平方，这意味着χ ' s(G)≤(4k−1)Δ−2k+ 1。
A strong edge coloring of a graph is a proper edge coloring where the edges at distance at most 2 receive distinct colors. Thestrong chromatic indexχ′s(G) of a graphGis the minimum number of colors used in a strong edge coloring ofG. In an orderingQof the vertices ofG, the back degree of a vertexxofGinQis the number of vertices adjacent tox, each of which has smaller index thanxinQ. Let G be a graph of maximum degree Δ and maximum average degree at most 2k. Yang and Zhu [J. Graph Theory,83, 334–339 (2016)] presented an algorithm that produces an ordering of the edges ofGin which each edge has back degree at most 4kΔ − 2kin the square of the line graph of G, implying that χ′s(G) ≤ 4kΔ − 2k+ 1. In this note, we improve the algorithm of Yang and Zhu by introducing a new procedure dealing with local structures. Our algorithm generates an ordering of the edges of G in which each edge has back degree at most (4k− 1)Δ − 2kin the square of the line graph of G, implying that χ′s(G) ≤ (4k− 1)Δ − 2k+ 1.