Adjacent Vertex Distinguishing Edge-Coloring of Planar Graphs with Girth at Least Five

Abstract

An adjacent vertex-distinguishing edge coloring ,avd-coloring for short, of a graph \(G\) is a proper edge coloring of \(G\) such that no pair of adjacent vertices are incident to the same set of colors. We denote the avd-chromatic number of \(G\) by \(\chi’_{avd}(G)\), which is the smallest integer \(k\) such that \(G\) has an avd-coloring with \(k\) colors, and the maximum degree of \(G\) by \(\Delta(G)\). In this paper, we prove that \(\chi’_{avd}(G) \leq \Delta(G) + 4\) for every planar graph \(G\) without isolated edges whose girth is at least five. Notably, this bound is nearly sharp, as \(\chi’_{avd}(C_5) = \Delta(C_5) + 3\).