On the neighbour-distinguishing index of a graph

被引：68

作者：

Edwards, Keith ^{[1
]}

Hornak, Mirko

Wozniak, Mariusz

机构：

[1] Univ Dundee, Div Appl Comp, Dundee DD1 4HN, Scotland

[2] PJ Sararik Univ, Inst Math, Kosice 04001, Slovakia

[3] AGH Univ Sci & Technol, Fac Appl Math, PL-30059 Krakow, Poland

来源：

GRAPHS AND COMBINATORICS | 2006年 / 22卷 / 03期

关键词：

D O I：

10.1007/s00373-006-0671-2

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

A proper edge colouring of a graph G is neighbour-distinguishing provided that it distinguishes adjacent vertices by sets of colours of their incident edges. It is proved that for any planar bipartite graph G with Delta(G) >= 12 there is a neighbour-distinguishing edge colouring of G using at most Delta(G) + 1 colours. Colourings distinguishing pairs of vertices that satisfy other requirements are also considered.

引用

页码：341 / 350

页数：10

共 16 条

[1] Balanced edge colorings [J].

Balister, PN ;

Kostochka, A ;

Li, H ;

Schelp, RH .

JOURNAL OF COMBINATORIAL THEORY SERIES B, 2004, 90 (01) :3-20

[2] Vertex distinguishing colorings of graphs with Δ (G)=2 [J].

Balister, PN ;

Bollobás, B ;

Schelp, RH .

DISCRETE MATHEMATICS, 2002, 252 (1-3) :17-29

[3]

BALISTER PN, 2002, ADJACENT VERTEX DIST

[4] Vertex-distinguishing edge colorings of graphs [J].

Ballister, PN ;

Riordan, OM ;

Schelp, RH .

JOURNAL OF GRAPH THEORY, 2003, 42 (02) :95-109

[5] On the vertex-distinguishing proper edge-colorings of graphs [J].

Bazgan, C ;

Harkat-Benhamdine, A ;

Li, H ;

Wozniak, M .

JOURNAL OF COMBINATORIAL THEORY SERIES B, 1999, 75 (02) :288-301

[6] A note on the vertex-distinguishing proper coloring of graphs with large minimum degree [J].

Bazgan, C ;

Harkat-Benhamdine, A ;

Li, H ;

Wozniak, M .

DISCRETE MATHEMATICS, 2001, 236 (1-3) :37-42

[7]

Burris A.C., 1993, THESIS MEMPHIS STATE

[8]

Burris AC, 1997, J GRAPH THEOR, V26, P73, DOI 10.1002/(SICI)1097-0118(199710)26:2<73::AID-JGT2>3.0.CO

[9]

2-C

[10]

Cerny J., 1996, Math. Slovaca, V46, P21

← 1 2 →