General neighbour-distinguishing index via chromatic number

An edge colouring of a graph G without isolated edges is neighbour-distinguishing if any two adjacent vertices have distinct sets consisting of colours of their incident edges. The general neighbour-distinguishing index of G is the minimum number gndi(G) of colours in a neighbour-distinguishing edge colouring of G. Gyori et al. [E. Gyori, M. Hornak, C. Palmer, M. Wozniak, General neighbour-distinguishing index of a graph, Discrete Math. 308 (2008) 827-831] proved that gndi(G) is an element of {2,3} provided G is bipartite and gave a complete characterisation of bipartite graphs according to their general neighbour-distinguishing index. The aim of this paper is to prove that if chi(G) >= 3, then [log(2) chi(G)] + 1 <= gndi(G) <= [log(2) chi(G)] + 2. Therefore, if log(2) chi(G) is not an element of Z, then gndi(G) = [log(2) chi(G)] + 1. (C) 2009 Elsevier B.V. All rights reserved.