Optimal Adjacent Strong Edge-Coloring of Circulant Graphs


Séminaire AMAC: CASC

13/02/2020 - 10:30 Hippolyte Signargout (ENS Lyon - LJK) Salle 106 - Batiment IMAG

A k-proper edge-coloring of a graph G is called adjacent strong if any pair of adjacent vertices are distinguished by the set of colors appearing in the edges incident to each vertex. The smallest value k for which G has such coloring is denoted by X'a(G). We prove that X'a(G)=2R+1 for the circulant graph G=Cn([[1,R]]) for most n and R.