Achromatic number versus pseudoachromatic number: A counterexample to a conjecture of Hedetniemi (Q1567683)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 1462336
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | Achromatic number versus pseudoachromatic number: A counterexample to a conjecture of Hedetniemi |
scientific article; zbMATH DE number 1462336 |
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
0.795557975769043
0 references
0.7953693866729736
0 references
0.7839016914367676
0 references
