On the algorithmic complexity of determining the AVD and NSD chromatic indices of graphs (Q2098173)

This paper is about two types of graph edge colorings, respectively called adjacent vertex distinguishing (AVD) and neighbor sum distinguishing (NSD) coloring. Both in AVD and NSD, the goal is to color the edges of a graph \(G\) in such a way that two incident edges are assigned different colors. In AVD, we have the following additional constraint: let \(u\) and \(v\) be two neighboring vertices in \(G\). Then the set \(S_u\) of colors given to edges incident to \(u\) must differ from the set \(S_v\) of colors given to edges incident to \(v\). In NSD, assuming each edge color is an integer, for any two neighbors \(u\) and \(v\) in \(G\), the sum of elements in \(S_u\) must differ from the sum of elements of \(S_v\). The AVD (resp. NSD) chromatic index of a graph \(G\), denoted \(\chi'_{\mathrm{AVD}}(G)\) (resp. \(\chi'_{\mathrm{NSD}}(G)\)), is the minimum number of colors needed to AVD (resp. NSD) color \(G\). It is conjectured that \(\chi'_{\mathrm{AVD}}(G)\) (resp. \(\chi'_{\mathrm{NSD}}(G)\)) lie in the interval \([\Delta(G);\Delta(G)+2]\), where \(\Delta(G)\) is the maximum degree of \(G\). The main results of the paper are NP-hardness proofs which basically show that, whenever \(\Delta(G)\geq 3\), (1) determining whether \(\chi'_{\mathrm{AVD}}(G)=\Delta(G)\) (resp. \(\chi'_{\mathrm{NSD}}(G)=\Delta(G)\)) is NP-hard, and (2) a similar result holds when \(\Delta(G)\) is replaced with \(\Delta(G)+1\). Besides, the authors show that there exist infinitely many graphs for which \(\chi'_{\mathrm{AVD}}(G)\neq \chi'_{\mathrm{NSD}}(G)\). As mentioned above, the paper is almost entirely turned towards proving NP-hardness of four problems, thus any reader not interested in these aspects should pass his/her way. Having said that, the paper is very carefully written, in the sense that the authors tried (and in my opinion, succeeded) to explain the different steps of the proofs in the most understandable way. The proofs are technical, but are nicely decomposed into ``elementary'' steps and are accompanied with nice illustrations. More than the proofs themselves, overall, the authors' style is pleasant. I also appreciated the contextualization and discussions all along the paper, and notably the detailed conclusion. All in all, a very pleasant paper.