We found a match
Your institution may have rights to this item. Sign in to continue.
- Title
A Note on Strong Edge Coloring of Sparse Graphs.
- Authors
Dong, Wei; Li, Rui; Xu, Bao Gang
- Abstract
A strong edge coloring of a graph is a proper edge coloring where the edges at distance at most 2 receive distinct colors. The strong chromatic index χ′s(G) of a graph G is the minimum number of colors used in a strong edge coloring of G. In an ordering Q of the vertices of G, the back degree of a vertex x of G in Q is the number of vertices adjacent to x, each of which has smaller index than x in Q. 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 of G in which each edge has back degree at most 4kΔ − 2k in 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)Δ − 2k in the square of the line graph of G, implying that χ′s(G) ≤ (4k − 1)Δ − 2k + 1.
- Subjects
SPARSE graphs; GRAPH coloring; GRAPH theory; GEOMETRIC vertices; EDGES (Geometry)
- Publication
Acta Mathematica Sinica, 2019, Vol 35, Issue 4, p577
- ISSN
1439-8516
- Publication type
Article
- DOI
10.1007/s10114-018-7186-7