Scribd
Upload
6 views3 pages

Chromatic Number Calculation for Graphs

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
6 views3 pages

Chromatic Number Calculation for Graphs

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

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 [Link], 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