Neighbor Sum Distinguishing Index of Subcubic Graphs

被引：4

作者：

Huo, Jingjing ^{[1
,2
]}

Wang, Weifan ^{[3
]}

Xu, Chuandong ^{[4
]}

机构：

[1] Suzhou Univ, Dept Math, Suzhou 215006, Peoples R China

[2] Hebei Univ Engn, Dept Math, Handan 056038, Peoples R China

[3] Zhejiang Normal Univ, Dept Math, Jinhua 321004, Peoples R China

[4] Northwestern Polytech Univ, Dept Appl Math, Sch Sci, Xian 710072, Shaanxi, Peoples R China

来源：

GRAPHS AND COMBINATORICS | 2017年 / 33卷 / 02期

关键词：

Subcubic graphs; Neighbor sum distinguishing edge coloring; Combinatorial Nullstellensatz; DISTINGUISHING EDGE-COLORINGS; PLANAR GRAPHS; COMBINATORIAL NULLSTELLENSATZ;

D O I：

10.1007/s00373-017-1760-0

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

A proper edge coloring of a graph G using the color set is called neighbor sum distinguishing if for any pair of adjacent vertices x and y the sum of colors taken on the edges incident to x is different from the sum of colors taken on the edges incident to y. The smallest value of k in such a coloring of G is denoted by . In this paper, we show that for any simple subcubic graph G. This improves a result in Flandrin et al. (Graphs Combin 29:1329-1336, 2013), which says that every cubic graph G has chi(Sigma)' (G) <= 8.

引用

页码：419 / 431

页数：13

共 16 条

[1] r-Strong edge colorings of graphs [J].

Akbari, S. ;

Bidkhori, H. ;

Nosrati, N. .

DISCRETE MATHEMATICS, 2006, 306 (23) :3005-3010

[2] Combinatorial Nullstellensatz [J].

Alon, N .

COMBINATORICS PROBABILITY & COMPUTING, 1999, 8 (1-2) :7-29

[3] 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

[4]

Bonamy M, 2014, ARXIV14083190V1

[5] Neighbor Sum Distinguishing Index [J].

Flandrin, Evelyne ;

Marczyk, Antoni ;

Przybylo, Jakub ;

Sacle, Jean-Francois ;

Wozniak, Mariusz .

GRAPHS AND COMBINATORICS, 2013, 29 (05) :1329-1336

[6] Δ+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

[7] On Neighbor-Distinguishing Index of Planar Graphs [J].

Hornak, Mirko ;

Huang, Danjun ;

Wang, Weifan .

JOURNAL OF GRAPH THEORY, 2014, 76 (04) :262-278

[8] Asymptotically Optimal Neighbour Sum Distinguishing Colourings of Graphs [J].

Przybylo, Jakub .

RANDOM STRUCTURES & ALGORITHMS, 2015, 47 (04) :776-791

[9] Neighbor Distinguishing Edge Colorings Via the Combinatorial Nullstellensatz Revisited [J].

Przybylo, Jakub ;

Wong, Tsai-Lien .

JOURNAL OF GRAPH THEORY, 2015, 80 (04) :299-312

[10] NEIGHBOR DISTINGUISHING EDGE COLORINGS VIA THE COMBINATORIAL NULLSTELLENSATZ [J].

Przybylo, Jakub .

SIAM JOURNAL ON DISCRETE MATHEMATICS, 2013, 27 (03) :1313-1322

← 1 2 →