General neighbour-distinguishing index of a graph (Q2470450)

A general \(k\)-edge-colouring of \(G\) is a mapping \(\phi\) from the edge set of \(G\) to the set \(\{1, 2, \dots , k\}\). The colour set (with respect to \(\phi\)) \(S_{\phi}(x)\) of a vertex \(x\) is the collection of values of \(\phi\) of edges incident to \(x\). The colouring \(\phi\) is neighbour-distinguishing if \(S_{\phi}(x) \neq S_{\phi}(y)\) whenever \(x, y\) are adjacent. The general neighbour-distinguishing index gndi(\(G\)) of \(G\) is the minimum \(k\) in a general \(k\)-edge-colouring of \(G\) that is neighbour-distinguishing. The main result proved in this paper is the following statement. If \(G\) is a graph without isolated edges, then gndi\((G) \leq 2 \lceil \log_2 \chi(G) \rceil + 1\).