Vertex distinguishing colorings of graphs with Δ(G)=2 Original Research Article

In a paper by Burris and Schelp (J. Graph Theory 26 (2) (1997) 70), a conjecture was made concerning the number of colors χs′(G) required to proper edge-color G so that each vertex has a distinct set of colors incident to it. We consider the case when Δ(G)=2, so that G is a union of paths and cycles. In particular we find the exact values of χs′(G) and hence verify the conjecture when G consists of just paths or just cycles. We also give good bounds on χs′(G) when G contains both paths and cycles.