An improved upper bound on the adjacent vertex distinguishing edge chromatic number of a simple graph

摘要

An adjacent vertex distinguishing edge coloring or an avd-coloring of a simple graph G is a proper edge coloring of G such that no two adjacent vertices are incident with the same set of colors that are used by them. H. Hatami showed that every simple graph G with no isolated edges and maximum degree △ has an avd-coloring with at most △ + 300 colors, provided that △ > 10~(20). We improve this bound as what follows: if △ > 10~(15), then the avd-chromatic number of G is at most △ + 180, where △ is the maximum degree of G.