Indexed by:
Abstract:
A coloring of the edges of a graph G is strong if each color class is an induced matching of G. The strong chromatic index of G, denoted by χ's(G), is the least number of colors in a strong edge coloring of G. Chang and Narayanan (J Graph Theory 73(2) (2013), 119–126) proved recently that χ's(G) ≤ 10 ∆ - 10 for a 2-degenerate graph G. They also conjectured that for any k-degenerate graph G there is a linear bound χ's(G) ≤ ck2 ∆, where c is an absolute constant. This conjecture is confirmed by the following three papers: in (G. Yu, Graphs Combin 31 (2015), 1815–1818), Yu showed that χ's(G) ≤ (4k-2) ∆ - k(2k-1) + 1. In (M. Debski, J. Grytczuk, M. Sleszynska-Nowak, Inf Process Lett 115(2) (2015), 326–330), Dȩbski, Grytczuk, and Śleszyńska-Nowak showed that χ's(G) ≤ (4k-1) ∆ - k(2k-1) + 1. In (T. Wang, Discrete Math 330(6) (2014), 17–19), Wang proved that χ's(G) ≤ (4k-2) ∆ - 2k2 + 1. If G is a partial k-tree, in (M. Debski, J. Grytczuk, M. Sleszynska-Nowak, Inf Process Lett 115(2) (2015), 326–330), it is proven that χ's(G) ≤ (k+1) (∆(G)+1). Let L(G) be the line graph of a graph G, and let L2(G) be the square of the line graph L(G). Then χ's(G) = χ(L2(G)). We prove that if a graph G has an orientation with maximum out-degree k, then L2(G) has coloring number at most 4k∆(G)-2k-1. If G is a k-tree, then L2(G) has coloring number at most (k+1) ∆ (G) - k(k+1)/2. As a consequence, a graph with Mad(G)≤2k has χ's(G) ≤ 4k∆(G)-2k-1, and a k-tree G has χ's(G) ≤ (k+1)∆(G)-k(k+1)/2. © 2015 Wiley Periodicals, Inc.
Keyword:
Reprint 's Address:
Email:
Source :
Journal of Graph Theory
ISSN: 0364-9024
Year: 2016
Issue: 4
Volume: 83
Page: 334-339
0 . 6 0 1
JCR@2016
0 . 9 0 0
JCR@2023
ESI HC Threshold:76
JCR Journal Grade:3
CAS Journal Grade:3
Cited Count:
SCOPUS Cited Count: 3
ESI Highly Cited Papers on the List: 0 Unfold All
WanFang Cited Count:
Chinese Cited Count:
30 Days PV: 4
Affiliated Colleges: