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.

05C15 Coloring of graphs and hypergraphs
05C38 Paths and cycles
Full Text: DOI