An Improved Upper Bound on the Adjacent Vertex Distinguishing Edge Chromatic Number of a Simple Graph

Abstract

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.

H. Hatami showed that every simple graph $G$ with no isolated
edges and maximum degree $\mathrm{\Delta }$ has an avd-coloring with at
most $\mathrm{\Delta }+300$ colors, provided that $\mathrm{\Delta }>{10}^{20}$.

We improve this bound as follows: if $\mathrm{\Delta }>{10}^{15}$, then the
avd-chromatic number of $G$ is at most $\mathrm{\Delta }+180$, where
$\mathrm{\Delta }$ is the maximum degree of $G$.