General neighbour-distinguishing index via chromatic number

An edge colouring of a graph GG 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 GG is the minimum number gndi(G) of colours in a neighbour-distinguishing edge colouring of GG. Győri et al. [E. Győri, M. Horňák, C. Palmer, M. Woźniak, General neighbour-distinguishing index of a graph, Discrete Math. 308 (2008) 827–831] proved that gndi(G)∈{2,3} provided GG 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 χ(G)≥3χ(G)≥3, then ⌈log2χ(G)⌉+1≤gndi(G)≤⌊log2χ(G)⌋+2. Therefore, if log2χ(G)∉Zlog2χ(G)∉Z, then gndi(G)=⌈log2χ(G)⌉+1.