On Neighbor-Distinguishing Index of Planar Graphs

被引：49

作者：

Hornak, Mirko ^{[1
]}

Huang, Danjun ^{[2
]}

Wang, Weifan ^{[2
]}

机构：

[1] PJ Safarik Univ Kosice, Inst Math, Kosice 04001, Slovakia

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

来源：

JOURNAL OF GRAPH THEORY | 2014年 / 76卷 / 04期

关键词：

color set; neighbor-distinguishing edge coloring; neighbor-distinguishing index; planar graph; DISTINGUISHING EDGE-COLORINGS;

D O I：

10.1002/jgt.21764

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

A proper edge coloring of a graph G without isolated edges is neighbor-distinguishing if any two adjacent vertices have distinct sets consisting of colors of their incident edges. The neighbor-distinguishing index of G is the minimum number ndi(G) of colors in a neighbor-distinguishing edge coloring of G. Zhang, Liu, and Wang in 2002 conjectured that ndi (G)(G)+2 if G is a connected graph of order at least 6. In this article, the conjecture is verified for planar graphs with maximum degree at least 12.

引用

页码：262 / 278

页数：17

共 10 条

[1]

[Anonymous], 2011, ELECT NOTES DISCRETE

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

[3]

Baril JL, 2006, AUSTRALAS J COMB, V35, P89

[4] On the neighbour-distinguishing index of a graph [J].

Edwards, Keith ;

Hornak, Mirko ;

Wozniak, Mariusz .

GRAPHS AND COMBINATORICS, 2006, 22 (03) :341-350

[5]

Greenhill C, 2006, ELECTRON J COMB, V13

[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] Adjacent vertex-distinguishing edge coloring of graphs with maximum degree Δ [J].

Hocquard, Herve ;

Montassier, Mickael .

JOURNAL OF COMBINATORIAL OPTIMIZATION, 2013, 26 (01) :152-160

[8] Adjacent vertex-distinguishing edge colorings of K4-minor free graphs [J].

Wang, Weifan ;

Wang, Yiqiao .

APPLIED MATHEMATICS LETTERS, 2011, 24 (12) :2034-2037

[9] Adjacent vertex distinguishing edge-colorings of graphs with smaller maximum average degree [J].

Wang, Weifan ;

Wang, Yiqiao .

JOURNAL OF COMBINATORIAL OPTIMIZATION, 2010, 19 (04) :471-485

[10] Adjacent strong edge coloring of graphs [J].

Zhang, ZF ;

Liu, LZ ;

Wang, JF .

APPLIED MATHEMATICS LETTERS, 2002, 15 (05) :623-626

← 1 →