On the neighbour-distinguishing index of a graph

Keith Edwards; Mirko Horňák; Mariusz Woźniak

doi:10.1007/s00373-006-0671-2

On the neighbour-distinguishing index of a graph

Keith Edwards
, Mirko Horňák
, Mariusz Woźniak

Research output: Contribution to journal › Article › peer-review

56 Citations (Scopus)

Abstract

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 ?(G) = 12 there is a neighbour-distinguishing edge colouring of G using at most ?(G)+1 colours. Colourings distinguishing pairs of vertices that satisfy other requirements are also considered.

Original language	English
Pages (from-to)	341-350
Number of pages	10
Journal	Graphs and Combinatorics
Volume	22
Issue number	3
DOIs	https://doi.org/10.1007/s00373-006-0671-2
Publication status	Published - 2006

Access to Document

10.1007/s00373-006-0671-2

Cite this

@article{901c12157b9a40a3aa6b363364b44d24,

title = "On the neighbour-distinguishing index of a graph",

abstract = "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 ?(G) = 12 there is a neighbour-distinguishing edge colouring of G using at most ?(G)+1 colours. Colourings distinguishing pairs of vertices that satisfy other requirements are also considered.",

author = "Keith Edwards and Mirko Hor{\v n}{\'a}k and Mariusz Wo{\'z}niak",

year = "2006",

doi = "10.1007/s00373-006-0671-2",

language = "English",

volume = "22",

pages = "341--350",

journal = "Graphs and Combinatorics",

issn = "0911-0119",

publisher = "Springer Japan",

number = "3",

}

TY - JOUR

T1 - On the neighbour-distinguishing index of a graph

AU - Edwards, Keith

AU - Horňák, Mirko

AU - Woźniak, Mariusz

PY - 2006

Y1 - 2006

N2 - 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 ?(G) = 12 there is a neighbour-distinguishing edge colouring of G using at most ?(G)+1 colours. Colourings distinguishing pairs of vertices that satisfy other requirements are also considered.

AB - 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 ?(G) = 12 there is a neighbour-distinguishing edge colouring of G using at most ?(G)+1 colours. Colourings distinguishing pairs of vertices that satisfy other requirements are also considered.

UR - https://www.scopus.com/pages/publications/33751530416

U2 - 10.1007/s00373-006-0671-2

DO - 10.1007/s00373-006-0671-2

M3 - Article

AN - SCOPUS:33751530416

SN - 0911-0119

VL - 22

SP - 341

EP - 350

JO - Graphs and Combinatorics

JF - Graphs and Combinatorics

IS - 3

ER -

On the neighbour-distinguishing index of a graph

Abstract

Access to Document

Other files and links

Fingerprint

Cite this