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

    Research output: Contribution to journalArticle

    8 Citations (Scopus)


    The pseudoachromatic number of a graph is the largest number of colours in a (not necessarily proper) vertex colouring of the graph such that every pair of distinct colours appears on the endpoints of some edge. The achromatic number is largest number of colours which can be used if the colouring must also be proper. Hedetniemi ( conjectured that these two parameters are equal for all trees. We disprove this conjecture by giving an infinite family of trees for which the pseudoachromatic number strictly exceeds the achromatic number.
    Original languageEnglish
    Pages (from-to)271-274
    Number of pages4
    JournalDiscrete Mathematics
    Issue number1-3
    Publication statusPublished - 28 May 2000


    Cite this