Download Victor Bryant-Aspects of Combinatorics_ a Wide-ranging Introduction-Cambridge University Press (1993) PDF

TitleVictor Bryant-Aspects of Combinatorics_ a Wide-ranging Introduction-Cambridge University Press (1993)
TagsDiscrete Mathematics Vertex (Graph Theory) Mathematical Relations Combinatorics
File Size10.2 MB
Total Pages274
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

Similer Documents