Vertex-distinguishing proper edge-colorings. (English) Zbl 0886.05068

Burris, A. C.; Schelp, R. H.

J. Graph Theory 26, No. 2, 73-82 (1997).

A proper edge-coloring of a graph \(G\) is vertex-distinguishing if, for each pair of distinct vertices \(u\) and \(v\), the set of colors assigned to the edges incident to \(u\) differs from the set of colors assigned to the edges incident to \(v\). Let \(n_i\) give the number of vertices of degree \(i\) in \(G\). The authors show that the minimum number of colors required for a vertex-distinguishing proper edge-coloring of a simple graph is bounded above by a constant multiplied by the maximum of the \(i\)th roots of the \(n_i\); the constant depends only upon the maximum degree of the graph. The bound is improved, for trees.

Reviewer: A.T.White (Kalamazoo)

MSC:

05C15	Coloring of graphs and hypergraphs
05C05	Trees

Keywords:

edge-coloring; bound; trees