Multi-set neighbor distinguishing 3-edge coloring

Abstract

Let G be a graph without isolated edges, and let c:E(G)→{1,…,k} be a coloring of the edges, where adjacent edges may be colored the same. The color code of a vertex v is the ordered k-tuple (a1,a2,…,ak), where ai is the number of edges incident with v that are colored i. If every two adjacent vertices of G have different color codes, such a coloring is called multi-set neighbor distinguishing. In this paper, we prove that three colors are sufficient to produce a multi-set neighbor distinguishing edge coloring for every graph without isolated edges.