Union vertex-distinguishing edge colorings

Abstract

The union vertex-distinguishing chromatic index ${\chi }_{\cup }^{\prime }(G)$ of a graph $G$ is the smallest natural number $k$ such that the edges of $G$ can be assigned nonempty subsets of $[k]$ so that the union of the subsets assigned to the edges incident to each vertex is different. We prove that ${\chi }_{\cup }^{\prime }(G)\in \left\{\lceil {\log }_2\left(n+1\right)\rceil ,\lceil {\log }_2\left(n+1\right)\rceil +1\right\}$ for a graph $G$ on $n$ vertices without a component of order at most two. This answers a question posed by Bousquet, Dailly, Duchêne, Kheddouci and Parreau, and independently by Chartrand, Hallas and Zhang.

8 pages, submitted