## 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
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.

## 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.