• Complex
  • Title
  • Keyword
  • Abstract
  • Scholars
  • Journal
  • ISSN
  • Conference
成果搜索

author:

Yang, D. (Yang, D..) [1] | Zhu, X. (Zhu, X..) [2]

Indexed by:

Scopus

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:

coloring number; line graph; maximum average degree of a graph; strong chromatic index

Community:

  • [ 1 ] [Yang, D.]Center for discrete mathematics, Fuzhou university, Fuzhou, Fujian 350003, China
  • [ 2 ] [Zhu, X.]Department of mathematics, Zhejiang normal university, Jinhua, Zhejiang 321004, China

Reprint 's Address:

Email:

Show more details

Related Keywords:

Related Article:

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:

WoS CC 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:

Online/Total:50/11077016
Address:FZU Library(No.2 Xuyuan Road, Fuzhou, Fujian, PRC Post Code:350116) Contact Us:0591-22865326
Copyright:FZU Library Technical Support:Beijing Aegean Software Co., Ltd. 闽ICP备05005463号-1