2026/08/05 by Gabriela Araujo-Pardo, Cristina Dalfó, Mónica Reyes
Mathematics · #math.CO
In this paper, we study proper and complete edge-colorings of Johnson graphs J(n,2), also called n-triangular graphs. They are isomorphic both to the 2-token graphs of complete graphs and to the line graphs of complete graphs. A t-edge-coloring of a graph G is a function that assigns one color from \1,2,…,t\ to each edge. Such a coloring is called proper if no two incident edges receive the same color, and complete if every pair of distinct colors appears on a pair of incident edges. The achromatic index, denoted by α2(G), is the largest integer t for which G admits a proper and complete t-edge-coloring. We establish new lower and upper bounds for α2(J(n,2)), provide explicit proper and complete edge-colorings attaining the lower bounds, and determine the exact value of α2(J(n,2)) for several values of n.