The Number of k-Coloured Graphs on Labelled Nodes

Abstract

By a labelled graph we shall mean a set of “nodes,“ distinguishable from one another and denoted by A₁, A₂, …, and a collection of “edges” viz., pairs of nodes. We say that an edge “joins” the pair of nodes which specifies it. We further stipulate that at most one edge joins any two nodes, and that no edge joins a node to itself.By a “colouring” of a graph in k colours we shall mean a mapping of the nodes of the graph onto a set of k colours C₁, C₂, …, C_k such that no two nodes which are joined by an edge are mapped onto the same colour. A graph so coloured in exactly k colours will be called a k-coloured graph. Since it is usually possible to colour a graph in more than one way, there will, in general, be many k-coloured graphs corresponding to a given graph.