The achromatic number of the union of paths (Q5937601)

When coloring the vertices of a graph adjacent vertices must get different colors. It is common to try to minimize the number of colors. The achromatic number seeks to maximize the number of colors, subject to the condition that every pair of distinct colors must appear at the ends of some edge. The graph is minimal with achromatic number \(n\) if every pair of colors appears at the ends of exactly one edge. NEWLINENEWLINENEWLINEThe authors consider the achromatic number of the disjoint union of paths of lengths \(a_1,\dots,a_k\). They show that it is the largest integer \(n\) such that \(a_1 + \dots + a_k \geq n(n-1)/2 + f(n,k)\), where \(f(n,k)\) is \(0\) if \(n\) is odd, or if \(n\) is even and \(k \geq n/2\), and it is \(n/2-k\) in the remaining case. They characterize the disjoint unions of paths that are minimal with achromatic number \(n\) and describe the relation with the harmonious chromatic number.