Discrete Mathematical Structures by Pearson

10-42 Discrete Mathematical Structures

Assign colour c

1

to the vertex v

1

of highest degree. The other vertex not adjacent to v

1

is v

3

,

and hence assign colour c

1

to v

3

. Now choose next vertex v

2

and assign it colour c

2

. The vertices

not adjacent to v

2

are v

4

and v

6

. Assign colour c

2

to v

4

. Next choose vertex v

5

and assign it colour

c

3

. The vertex not adjacent to v

5

is v

7

, and therefore assigns colour c

3

to v

7

. The vertex v

6

can be

assigned colour c

4

. Hence, chromatic number of graph G is 4.

Example 2  Use Welch and Powell algorithm to colour the vertices of the graph (Fig. 10.56)

having 12 vertices with minimum number of colours.

c

2

c

4

c

2

c

4

b

c

3