Abstract:
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.