Achromatic number versus pseudoachromatic number: A counterexample to a conjecture of Hedetniemi (Q1567683)

From MaRDI portal
scientific article
Language Label Description Also known as
English
Achromatic number versus pseudoachromatic number: A counterexample to a conjecture of Hedetniemi
scientific article

    Statements

    Achromatic number versus pseudoachromatic number: A counterexample to a conjecture of Hedetniemi (English)
    0 references
    21 June 2000
    0 references
    The achromatic number of a graph \(G\) is the largest number of colors in a proper vertex coloring of \(G\) so that each pair of distinct colors appear on the end vertices of some edge. The pseudoachromatic number is the corresponding parameter for not necessarily proper vertex colorings. Hedetniemi (\url{http://cyclone.cs.clemson.edu/~hedet/coloring.html}) conjectured that the two parameters agree for all trees. The present author disproves this conjecture by constructing an infinite family of trees for which the pseudoachromatic number is greater than the achromatic number.
    0 references
    0 references
    conjecture of Hedetniemi
    0 references
    achromatic number
    0 references
    vertex coloring
    0 references
    pseudoachromatic number
    0 references
    trees
    0 references
    0 references
    0 references