(a) Determine the rook polynomial of the given board of shaded squares. (You may useany method of your choice.) (b) Radio stations broadcast their signal at certain frequencies. There are a limitednumber of frequencies to choose from, so many stations use the same frequency aslong as they are positioned far enough apart not to cause interference. The following8 stations A,..., H wish to broadcast in a particular region. The radio stations thatare close enough to each other to cause interference are given in the table below. (i) Represent this information as a graph G with vertices as the stations and edges when two stations are close enough to cause interference. (ii) Give with reasons, non-trivial upper and lower bounds on x(G) and find a minimum vertex colouring. Hence determine the minimum number of frequencies that are required. Write down a vertex decomposition of the graph to assign the radio stations to the frequencies.(5 marka) (iii) Suppose a new radio station, I, wishes to broadcast. Due to location this cannot share a frequency with D, E or G. Is it possible for this new station to broadcast using the minimum number of frequencies determined in (ii). Explain, with full reasons, if this is not possible and give a vertex decomposition if it is possible.

Fig: 1

Fig: 2

Fig: 3

Fig: 4

Fig: 5

Fig: 6

Fig: 7

Fig: 8