The achromatic number of the union of paths (Q5937601)
From MaRDI portal
scientific article; zbMATH DE number 1619852
Language | Label | Description | Also known as |
---|---|---|---|
English | The achromatic number of the union of paths |
scientific article; zbMATH DE number 1619852 |
Statements
The achromatic number of the union of paths (English)
0 references
17 February 2002
0 references
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. The 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.
0 references
achromatic number
0 references
harmonious chromatic number
0 references