A vertex colouring of a graph is an assignment of colours to the vertices, with the requirement that adjacent vertices receive distinct colours.
A harmonious colouring is a vertex colouring with the added requirement that each pair of colours appears together on at most one edge. The harmonious chromatic number of a graph is the minimum number of colours in a harmonious colouring of the graph.
A closely related concept is the achromatic number of a graph, which is the greatest number of colours in a vertex colouring such that for each pair of colours, there is at least one edge whose endpoints have those colours. Such a colouring is called a complete colouring.
Click here for a bibliography of papers on harmonious colourings and achromatic number, last updated 10 January 2017. This is also available as a pdf file. It is intended to be a comprehensive list; please email me if you know of any omissions or errors, or if you would like a copy of the LaTeX source file.
A vertex colouring is called an exact colouring if each pair of colours appears together on exactly one edge. A colouring is exact if and only if it is both harmonious and complete.
It is easy to see that a graph has an exact colouring with n colours precisely if it is a detachment of the complete graph on n vertices.
Back to my home page.