Adjacent vertex distinguishing edge colorings of planar graphs with girth at least five
An adjacent vertex distinguishing edge coloring of a graph \(G\) is a proper edge coloring of \(G\) such that any pair of adjacent vertices admit different sets of colors. The minimum number of colors required for such a coloring of \(G\) is denoted by \(\chi ^{\prime }_{a}(G)\). In this paper, we prove that if \(G\) is a planar graph with girth at least 5 and \(G\) is not a 5-cycle, then \(\chi ^{\prime }_{a}(G)\le \Delta +2\), where \(\Delta \) is the maximum degree of \(G\). This confirms partially a conjecture in Zhang et al. (Appl Math Lett 15:623626, 2002).
adjacent vertex distinguishing edge coloring planar graph girth maximum degree