Scribd
Upload
7 views3 pages

Maths Module5

The document analyzes the chromatic numbers of three different graphs. For graph (a), the chromatic number is 2; for graph (b), it is 4; and for graph (c), it is 3. The proper colorings are explained for each graph based on the adjacency of the vertices.

Uploaded by

nehavijaya12
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
7 views3 pages

Maths Module5

The document analyzes the chromatic numbers of three different graphs. For graph (a), the chromatic number is 2; for graph (b), it is 4; and for graph (c), it is 3. The proper colorings are explained for each graph based on the adjacency of the vertices.

Uploaded by

nehavijaya12
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 3

Example 1: Find the chromatic number of each of the following graphs.

v5 v4

v6 v3

v1 v2 a
(i) For the graph (a), let us assign a colour α to the vertex v1.Then, for a proper
colouring. we have to assign a different colour to its neighbours v2,v4,v6. Since
v2,v4,v6 are mutually nonadjacent vertices, they can have the same colour, say β(
which is different from α ). Since v3, v5 are not adjacent to v1 these can have the
same colour as v₁, namely α.
Thus, the graph can be property coloured with at least two colours, with the
vertices v1, v3,v5 having one colour α, and v2,v4,v6 having a different colour β .
Hence, the chromatic number of the graph is 2.
(ii) For the graph (b), let us assign the colour αto the vertex v₁. Then, for a proper
colouring,its neighbours v2, v3 and v4 cannot have the colour α , but v5 can have
the colour α. Furthermore, v2, v3, v4 must have different colours, say β, y, δ. Thus,
at least four colours are required for a proper colouring of the graph. Hence the
chromatic number of the graph is 4.

v2

v1 v3 v5

v4 b
(iii) For the graph (c), we can assign the same colour, say α, to the non-
adjacent vertices v1, v3,v5. Then the vertices v2,v4,v6 can be assigned the
same colour other than α.Suppose we assign a colour β to v2,v4,v6.
Consequently v7 and v8 can be assigned the same colour which is
different from both α and β.Thus, a minimum of three colours are needed
for a proper colouring of the graph. Hence its chromatic number is 3.
v1 v8
v2
v6
v7

v5 v3

v4 c

You might also like