##### Document Text Contents

Page 2

ASPECTS OF COMBINATORICS

Page 138

Vertex-colourings

The next question we ask is not how many colours are needed for a vertex-

colouring but, given some specific colours, in how many different ways the vertex-

colouring can be done.

Example Let G be the graph shown. Illustrate the number of different ways of

vertex-colouring G with three colours 1, 2 and 3.

Find a formulafor the number of ways of vertex-colouring G in k given colours.

Solution It is very straightforward to find the different vertex-colourings of G in

the three given colours; there are 18 ways in all, as illustrated:

2 3 2 3 2 3 3 2 3 2 3 2

A3 43 3 3A 3A 3A

3 1 2 1 2 3 3 2 3 1 2

To find a formula for the number of ways of vertex-colouring G in

k given colours it is convenient to distinguish two types of colourings, u

the first type in which the vertices u and v (as shown on the right) are

of the same colour and the second type where u and v are of different

colours. For this particular graph it is then easy to count the number

of vertex-colourings of each type and to add the two totals together: v

u and v of different colours

Let G1 be the graph obtained from G by adding the edge uv. Then vertex-colouring

G with u and v of different colours is clearly equivalent to vertex-colouring G1. We

131

ASPECTS OF COMBINATORICS

Page 138

Vertex-colourings

The next question we ask is not how many colours are needed for a vertex-

colouring but, given some specific colours, in how many different ways the vertex-

colouring can be done.

Example Let G be the graph shown. Illustrate the number of different ways of

vertex-colouring G with three colours 1, 2 and 3.

Find a formulafor the number of ways of vertex-colouring G in k given colours.

Solution It is very straightforward to find the different vertex-colourings of G in

the three given colours; there are 18 ways in all, as illustrated:

2 3 2 3 2 3 3 2 3 2 3 2

A3 43 3 3A 3A 3A

3 1 2 1 2 3 3 2 3 1 2

To find a formula for the number of ways of vertex-colouring G in

k given colours it is convenient to distinguish two types of colourings, u

the first type in which the vertices u and v (as shown on the right) are

of the same colour and the second type where u and v are of different

colours. For this particular graph it is then easy to count the number

of vertex-colourings of each type and to add the two totals together: v

u and v of different colours

Let G1 be the graph obtained from G by adding the edge uv. Then vertex-colouring

G with u and v of different colours is clearly equivalent to vertex-colouring G1. We

131