### Abstract

Original language | English |
---|---|

Pages (from-to) | 271-274 |

Number of pages | 4 |

Journal | Discrete Mathematics |

Volume | 219 |

Issue number | 1-3 |

DOIs | |

Publication status | Published - 28 May 2000 |

### Fingerprint

### Cite this

}

*Discrete Mathematics*, vol. 219, no. 1-3, pp. 271-274. https://doi.org/10.1016/S0012-365X(00)00025-X

**Achromatic number versus pseudoachromatic number : A counterexample to a conjecture of Hedetniemi.** / Edwards, Keith J.

Research output: Contribution to journal › Article

TY - JOUR

T1 - Achromatic number versus pseudoachromatic number

T2 - A counterexample to a conjecture of Hedetniemi

AU - Edwards, Keith J.

N1 - Copyright 2004 Elsevier Science B.V., Amsterdam. All rights reserved.

PY - 2000/5/28

Y1 - 2000/5/28

N2 - 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 (http://cyclone.cs.clemson.edu/~hedet/coloring.html) 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.

AB - 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 (http://cyclone.cs.clemson.edu/~hedet/coloring.html) 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.

UR - http://www.scopus.com/inward/record.url?scp=0347646985&partnerID=8YFLogxK

U2 - 10.1016/S0012-365X(00)00025-X

DO - 10.1016/S0012-365X(00)00025-X

M3 - Article

VL - 219

SP - 271

EP - 274

JO - Discrete Mathematics

JF - Discrete Mathematics

SN - 0012-365X

IS - 1-3

ER -