Neighbor sum distinguishing edge colorings of graphs with bounded maximum average degree

被引:0
作者
Dong, Aijun [1 ]
Wang, Guanghui [2 ]
Zhang, Jianghua [3 ]
机构
[1] Shandong Jiaotong Univ, Sch Sci, Jinan 250023, Peoples R China
[2] Shandong Univ, Sch Math, Jinan 250100, Peoples R China
[3] Shandong Univ, Sch Management, Jinan 250100, Peoples R China
基金
高等学校博士学科点专项科研基金; 中国国家自然科学基金;
关键词
Proper colorings; Neighbor sum distinguishing edge colorings; Maximum average degree; DISTINGUISHING INDEX;
D O I
10.1016/j.dam.2013.10.009
中图分类号
O29 [应用数学];
学科分类号
070104 ;
摘要
dA proper lkl-edge coloring of a graph G is a proper edge coloring of G using colors of the set [k], where [k] = {1, 2,..., k}. A neighbor sum distinguishing vertical bar k vertical bar-edge coloring of G is a proper [k]-edge coloring of G such that, for each edge uv is an element of E(G), the sum of colors taken on the edges incident with u is different from the sum of colors taken on the edges incident with u. By ndi Sigma(G), we denote the smallest value k in such a coloring of G. The average degree of a graph G is Sigma vEV(G)d(v)/vertical bar V(G)vertical bar; we denote it by ad(G). The maximum average degree mad(G) of G is the maximum of average degrees of its subgraphs. In this paper, we show that, if G is a graph without isolated edges and mad(G) < 5/2, then ndi Sigma(G) <= k, where k = max {Delta(G) + 1, 6}. This partially confirms the conjecture proposed by Flandrin et al. (C) 2013 Elsevier B.V. All rights reserved.
引用
收藏
页码:84 / 90
页数:7
相关论文
共 22 条
[1]   Degree constrained subgraphs [J].
Addario-Berry, L. ;
Dalal, K. ;
Reed, B. A. .
DISCRETE APPLIED MATHEMATICS, 2008, 156 (07) :1168-1174
[2]   Vertex-colouring edge-weightings [J].
Addario-Berry, Louigi ;
Dalal, Ketan ;
McDiarmid, Colin ;
Reed, Bruce A. ;
Thomason, Andrew .
COMBINATORICA, 2007, 27 (01) :1-12
[3]   r-Strong edge colorings of graphs [J].
Akbari, S. ;
Bidkhori, H. ;
Nosrati, N. .
DISCRETE MATHEMATICS, 2006, 306 (23) :3005-3010
[4]   Adjacent vertex distinguishing edge-colorings [J].
Balister, P. N. ;
Gyori, E. ;
Lehel, J. ;
Schelp, R. H. .
SIAM JOURNAL ON DISCRETE MATHEMATICS, 2007, 21 (01) :237-250
[5]  
Bondy J. A., 1976, Graduate Texts in Mathematics, V290
[6]  
Bu Y., 2011, DISCUSS MATH GRAPH T, V31, P429, DOI [10.7151/dmgt.1556, DOI 10.7151/DMGT.1556]
[7]   NEIGHBOR SUM DISTINGUISHING COLORING OF SOME GRAPHS [J].
Dong, Aijun ;
Wang, Guanghui .
DISCRETE MATHEMATICS ALGORITHMS AND APPLICATIONS, 2012, 4 (04)
[8]   On the neighbour-distinguishing index of a graph [J].
Edwards, Keith ;
Hornak, Mirko ;
Wozniak, Mariusz .
GRAPHS AND COMBINATORICS, 2006, 22 (03) :341-350
[9]   Neighbor Sum Distinguishing Index [J].
Flandrin, Evelyne ;
Marczyk, Antoni ;
Przybylo, Jakub ;
Sacle, Jean-Francois ;
Wozniak, Mariusz .
GRAPHS AND COMBINATORICS, 2013, 29 (05) :1329-1336
[10]   Δ+300 is a bound on the adjacent vertex distinguishing edge chromatic number [J].
Hatami, H .
JOURNAL OF COMBINATORIAL THEORY SERIES B, 2005, 95 (02) :246-256