# zbMATH — the first resource for mathematics

Vertex distinguishing colorings of graphs with $$\Delta(G)=2$$. (English) Zbl 1005.05019
Authors’ abstract (extended): In a paper by A. C. Burris and R. H. Schelp [J. Graph Theory 26, 73-82 (1997; Zbl 0886.05068)], a conjecture was made concerning the number of colors $$\chi_s'(G)$$ required to proper edge-color $$G$$ so that each vertex has a distinct set of colors incident to it: if $$G$$ is a graph with no more than one isolated vertex and no isolated edges and $$k$$ is the smallest integer such that $${k\choose d}\geq n_d$$, the number of vertices of degree $$d$$ in $$G$$, for all $$d$$ such that $$\delta(G)\leq d\leq\Delta(G)$$, then $$\chi_s'(G)= k$$ or $$k+1$$. We consider the case when $$\Delta(G)= 2$$, so that $$G$$ is a union of paths and cycles. In particular we find the exact values of $$\chi_s'(G)$$ and hence verify the conjecture when $$G$$ consists of just paths or just cycles. We also give good bounds on $$\chi_s'(G)$$ when $$G$$ contains both paths and cycles.

##### MSC:
 05C15 Coloring of graphs and hypergraphs 05C38 Paths and cycles
##### Keywords:
edge-color; paths and cycles
Full Text: