|
|||||
|
|
On the Neighbour-Distinguishing Index of a Graph |
|
| Authors: | Keith Edwards Mirko Horňák Mariusz Wo?niak |
| Institution: | (1) Division of Applied Computing, University of Dundee, Dundee, DD1 4HN, UK;(2) Institute of Mathematics, P. J. Šafárik University, Jesenná 5, 040 01 Košice, Slovakia;(3) Faculty of Applied Mathematics, AGH University of Science and Technology, Al. Mickiewicza 30, 30-059 Kraków, Poland |
| 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. |
| Keywords: | |
| 本文献已被 SpringerLink 等数据库收录！ | |