Question

11. (10 pts) Consider the interval graph defined by the following intervals: [0,10] [.25,1] [.5,2] [1.5,3] [1.75,5] [8,9] [8.5,8.75]. (a) Draw the graph and find its chromatic number. (b) Color it using the First Fit algorithm.

Answer 1

11)

a)

AS per the given points

A = [0,10]

B= [0.25, 1]

C= [0.5, 2]

D =[1.5, 3]

E =[1.75, 5]

F= [8, 9]

G =[8.5, 8.75]

The below is the INVERVAL GRAPH for the following points or vertices.

In order to find the chromatic number let us draw the rough figure for the given vertices.

then we need assign colours with No two adjacent vertices have same colour.

After assigning the colours then we need to count the total number of colours we had assigned , Hence this count value gives us the CHROMATIC NUMBER.

In this case the chromatic number is equal to 4.

A B o С D E Chromatic Number = 4

b)

COLOURING USING FIRST FIT ALGORITHM.

Based on the first fit algorithm

Form the below figure

we can see that at vertex D we any colour other than BLUE OR GREEN can we given but as per the first fit algorithm we have to assign ORANGE COLOUR .

SIMILARLY AT VERTEX F we can give any colour other than blue but

WE need to follow the preference order so VERTEX F is assigned with orange colour

similarly VERTEX G is assigned with GREEN

A B #1 BLUE 1 2 3 #2 ORANGE G #3 GREEN #4 BROWN 3 С F 2 A Chromatic Number = 4

IF you are satisfied with the solution please give it a THUMBS UP!!