Hostname: page-component-586b7cd67f-2brh9 Total loading time: 0 Render date: 2024-11-22T15:07:56.707Z Has data issue: false hasContentIssue false
  • English
  • Français

The Number of k-Coloured Graphs on Labelled Nodes

Published online by Cambridge University Press:  20 November 2018

R. C. Read
R. C. Read*
Affiliation:
University College of the West Indies
Rights & Permissions [Opens in a new window]

Extract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

By a labelled graph we shall mean a set of “nodes,“ distinguishable from one another and denoted by A1, A2, …, 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 C1, C2, …, Ck 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.

Type
Research Article
Information
Canadian Journal of Mathematics , Volume 12 , 1960 , pp. 410 - 414
Copyright
Copyright © Canadian Mathematical Society 1960

References

1. Whitney, H., A Logical expansion in mathematics, Bull. Amer. Math. Soc, 54 (1932), 339–362.Google Scholar
2. Gilbert, E.N., Enumeration of labelled graphs, Can. J. Math., 5 (1956), 405–411.Google Scholar