×

The harmonious chromatic number and the achromatic number. (English) Zbl 0882.05062

Bailey, R. A. (ed.), Surveys in combinatorics, 1997. Proceedings of the 16th British combinatorial conference, London, UK, July 1997. London: Cambridge University Press. Lond. Math. Soc. Lect. Note Ser. 241, 13-47 (1997).
Summary: The harmonious chromatic number of a graph is the least number of colours in a vertex colouring such that each pair of colours appears on at most one edge. The achromatic number of a graph is the greatest number of colours in a vertex colouring such that each pair of colours appears on at least one edge. This paper is a survey of what is known about these two parameters, in particular we look at upper and lower bounds, special classes of graphs and complexity issues.
For the entire collection see [Zbl 0869.00029].

MSC:

05C15 Coloring of graphs and hypergraphs
68Q25 Analysis of algorithms and problem complexity
05C05 Trees
PDFBibTeX XMLCite