zbMATH — the first resource for mathematics

Vertex-distinguishing proper edge-colorings. (English) Zbl 0886.05068
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.

MSC:
 05C15 Coloring of graphs and hypergraphs 05C05 Trees
Keywords:
edge-coloring; bound; trees
Full Text: