Harmonious Colourings and Achromatic Number

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 8 September 2022. 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.

Detachments and Exact Colourings

Another related concept is a detachment of a graph. A detachment of a graph G is formed by splitting each vertex into one or more subvertices, and sharing the incident edges arbitrarily among the subvertices. Thus a detachment of G has at least as many vertices as G, and the same number of edges as G.

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.