Optimal Adjacent Vertex-Distinguishing Edge-Colorings of Circulant Graphs

2020/04/27 by Sylvain Gravier, Gravier, Sylvain, Hippolyte Signargout +3
Computer Science · Mathematics · #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #cs.DM #math.CO

paper · pdf · doi:10.48550/arxiv.2004.12822

Editor-neutral version

arxiv created 2022/01/04 · arxiv updated 2022/01/05

Abstract

A k-proper edge-coloring of a graph G is called adjacent vertex-distinguishing if any two adjacent vertices are distinguished by the set of colors appearing in the edges incident to each vertex. The smallest value k for which G admits such coloring is denoted by χ'_a(G). We prove that χ'_a(G) = 2R + 1 for most circulant graphs C_n([1, R]).

Related

• An improved upper bound on the adjacent vertex distinguishing chromatic index of a graph
• A Vizing-like theorem for union vertex-distinguishing edge coloring
• Adjacent Vertex Distinguishing Total Coloring of Corona Product of Graphs
• The adjacent vertex distinguishing total chromatic number
• Distinguishing chromatic number of Hamiltonian circulant graphs