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

author:

Yang, Daqing (Yang, Daqing.) [1] | Zhu, Xuding (Zhu, Xuding.) [2]

Indexed by:

EI Scopus SCIE

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:

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

Community:

  • [ 1 ] [Yang, Daqing]Fuzhou Univ, Ctr Discrete Math, Fuzhou 350003, Fujian, Peoples R China
  • [ 2 ] [Zhu, Xuding]Zhejiang Normal Univ, Dept Math, Jinhua 321004, Zhejiang, Peoples R China

Reprint 's Address:

  • 杨大庆

    [Yang, Daqing]Fuzhou Univ, Ctr Discrete Math, Fuzhou 350003, Fujian, Peoples R China

Show more details

Version:

Related Keywords:

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

Online/Total:321/11071090
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