A Vizing-like theorem for union vertex-distinguishing edge coloring
This work provides a theoretical characterization for a new graph coloring variant, offering exact results for specific graph families, but the problem is niche and the results are incremental.
The paper introduces a variant of vertex-distinguishing edge coloring where each edge gets a subset of colors and vertex labels are unions of incident edge color sets. It proves that for any graph (excluding trivial components), the minimum number of colors needed is one of only three values depending on the graph's order, and gives exact values for paths, cycles, and complete binary trees.
We introduce a variant of the vertex-distinguishing edge coloring problem, where each edge is assigned a subset of colors. The label of a vertex is the union of the sets of colors on edges incident to it. In this paper we investigate the problem of finding a coloring with the minimum number of colors where every vertex receives a distinct label. Finding such a coloring generalizes several other well-known problems of vertex-distinguishing colorings in graphs.We show that for any graph (without connected component reduced to an edge or a single vertex), the minimum number of colors for which such a coloring exists can only take 3possible values depending on the order of the graph. Moreover, we provide the exact value for paths, cycles and complete binary trees.