Adjacent vertex distinguishing edge-colorings

Abstract. An adjacent vertex distinguishing edge-coloring of a simple graph G is a proper edge-coloring of G such that no pair of adjacent vertices meets the same set of colors. The minimum number of colors χ′a(G) required to give G an adjacent vertex distinguishing coloring is studied for graphs with no isolated edge. We prove χ′a(G) ≤ 5 for such graphs with maximum degree ∆(G) = 3 and χ′a(G) ≤ ∆(G) + 2 for bipartite graphs. These bounds are tight. For k-chromatic graphs G without isolated edges we prove a weaker result of the form χ′a(G) = ∆(G) +O(log k). 1