Union vertex-distinguishing edge colorings

2023/03/05 by Kittipassorn, Teeradej, Sanyatit, Preechaya
#05C05 (Secondary) #05C15 (Primary) 05C35 #05C78 #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics

paper · doi:10.48550/arxiv.2303.02757

Abstract

The union vertex-distinguishing chromatic index χ'_∪(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 χ'_∪(G) ∈ \ \lceil log₂(n +1) \rceil, \lceil log₂(n +1) \rceil+1 \ 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.

Related

• A Vizing-like theorem for union vertex-distinguishing edge coloring
• The chromatic distinguishing index of certain graphs
• Vertex-distinguishing edge coloring of graphs
• An improved upper bound on the adjacent vertex distinguishing chromatic index of a graph
• Vertex-distinguishing and sum-distinguishing edge coloring of regular graphs