Achromatic number versus pseudoachromatic number: A counterexample to a conjecture of Hedetniemi
type: Item
instance of: scholarly article
title: Achromatic number versus pseudoachromatic number: A counterexample to a conjecture of Hedetniemi
zbMATH Open document ID: 0948.05026
DOI: 10.1016/S0012-365X(00)00025-X
published in: Discrete Mathematics
publication date: 2000-06-21T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 05C15
zbMATH DE Number: 1462336
zbMATH Keywords: conjecture of Hedetniemi
zbMATH Keywords: achromatic number
zbMATH Keywords: vertex coloring
zbMATH Keywords: pseudoachromatic number
zbMATH Keywords: trees
author: Keith Edwards
reviewed by: Arthur T. White
MaRDI profile type: Publication
Wikidata QID: Q123162527
full work available at URL: s0012-365x(00)00025-x
OpenAlex ID: W2026543669
description: scientific article; zbMATH DE number 1462336