Achromatic number versus pseudoachromatic number: A counterexample to a conjecture of Hedetniemi
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.
- Inequalities involving the irredundance number of a graph
- scientific article; zbMATH DE number 3906522 (Why is no real title available?)
- My top 10 graph theory conjectures and open problems
- Achromatic colorings of polarity graphs
- On criticality and additivity of the pseudoachromatic number under join
- The achromatic number and the pseudoachromatic number of caterpillars
- Parameterized Reunion with achromatic number
- Complete partitions of graphs
This page was built for publication: Achromatic number versus pseudoachromatic number: A counterexample to a conjecture of Hedetniemi
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1567683)
