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

    Identifiers