Good edge-labelling of graphs

A good edge-labelling   of a graph GG is a labelling of its edges such that, for any ordered pair of vertices (x,y)(x,y), there do not exist two paths from xx to yy with increasing labels. This notion was introduced by Bermond et al. (2009) [2] to solve wavelength assignment problems for specific categories of graphs. In this paper, we aim at characterizing the class of graphs that admit a good edge-labelling. First, we exhibit infinite families of graphs for which no such edge-labelling can be found. We then show that deciding whether a graph GG admits a good edge-labelling is NP-complete, even if GG is bipartite. Finally, we give large classes of graphs admitting a good edge-labelling: C3C3-free outerplanar graphs, planar graphs of girth at least 6, {C3,K2,3}{C3,K2,3}-free subcubic graphs and {C3,K2,3}{C3,K2,3}-free ABC-graphs.

► Deciding whether a graph admits a good-edge labelling is NP-complete.
► Sufficient conditions for a graph to have a good-edge labelling.
► Every graph, every subgraph HH of which has at most 3/2|V(H)|−1/23/2|V(H)|−1/2 edges, has a good edge labelling unless it contains C3C3 or K2,3K2,3.