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 chi(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 chi(s)' (G) <= 10 Delta - 10 for a 2-degenerate graph G. They also conjectured that for any k-degenerate graph G there is a linear bound chi(s)' (G) <= ck(2)Delta, 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 chi(s)' (G) <= (4k - 2)Delta - k(2k - 1) + 1. In (M. Debski, J. Grytczuk, M. Sleszynska-Nowak, Inf Process Lett 115(2) (2015), 326-330), Debski, Grytczuk, and Sleszynska-Nowak showed that chi(s)' (G) <= (4k - 1)Delta - k(2k + 1) + 1. In (T. Wang, Discrete Math 330(6) (2014), 17-19), Wang proved that chi(s)' (G) <= (4k - 2)Delta - 2k(2) + 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 chi(s)' (G) <= (k + 1)(Delta(G) + 1). Let L(G) be the line graph of a graph G, and let L-2(G) be the square of the line graph L(G). Then chi(s)' (G) = chi(L-2(G)). We prove that if a graph G has an orientation with maximum out-degree k, then L-2(G) has coloring number at most 4k Delta(G) - 2k - 1. If G is a k-tree, then L-2(G) has coloring number at most (k + 1)Delta(G) - k(k+ 1)/2. As a consequence, a graph with Mad(G) <= 2k has chi(s)' (G) = 4k Delta(G) - 2k - 1, and a k-tree G has chi(s)' (G) <= (k + 1)Delta(G) - k(k+ 1)/2. (C) 2015 Wiley Periodicals, Inc.
Keyword:
Reprint 's Address:
Email:
Version:
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 Discipline: MATHEMATICS;
ESI HC Threshold:76
JCR Journal Grade:3
CAS Journal Grade:3
Cited Count:
WoS CC Cited Count: 3
SCOPUS Cited Count: 3
ESI Highly Cited Papers on the List: 0 Unfold All
WanFang Cited Count:
Chinese Cited Count:
30 Days PV: 1
Affiliated Colleges: