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
conjecture of Hedetniemi
0 references
achromatic number
0 references
vertex coloring
0 references
pseudoachromatic number
0 references
trees
0 references