Premium
Vertex‐distinguishing proper edge‐colorings
Author(s) -
Burris A. C.,
Schelp R. H.
Publication year - 1997
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/(sici)1097-0118(199710)26:2<73::aid-jgt2>3.0.co;2-c
Subject(s) - combinatorics , mathematics , vertex (graph theory) , simple graph , edge coloring , graph , complete coloring , fractional coloring , colored , discrete mathematics , graph power , line graph , materials science , composite material
An edge‐coloring is called vertex‐distinguishing if every two distinct vertices are incident to different sets of colored edges. The minimum number of colors required for a vertex‐distinguishing proper edge‐coloring of a simple graph G is denoted by $\chi^\prime_s(G)$ . A simple count shows that $\chi^{\prime}_{s}(G) \geq \max\{(i!n_{i})^{1/i} : 1 \leq i \leq \Delta \}$ where n i denotes the number of vertices of degree i in G . We prove that $\chi_s^{\prime}(G) \leq C\max \{n^{1/i}_{i} : 1 \leq i \leq \Delta \}$ where C is a constant depending only on Δ. Some results for special classes of graphs, notably trees, are also presented. © 1997 John Wiley & Sons, Inc. J Graph Theory 26: 73–82, 1997