Subjects
Grades
The chromatic number of a graph is the minimum number of colours that must be used to colour all the vertices of a graph, making sure that two adjacent vertices are not the same colour.
Coloured graphs and chromatic numbers are used to solve planning problems when certain incompatibilities must be taken into account.
The following situations are examples of where it can be useful to find the chromatic number: scheduling, classifying species of animals or plants, colouring countries on a world map, etc.
Steps to solve a problem using a chromatic number:
Draw a graph that represents the situation where the vertices are the different elements and the edges illustrate the incompatibilities between those elements.
List the vertices of the graph in decreasing order of degree (the order does not matter for two vertices that have the same degree).
Colour the first vertex of the list (the one with the highest degree) with any colour.
Moving down the list, assign the same colour to the other vertices that are not connected to the first vertex or to each other.
Repeat steps 3 and 4 with a new colour each time until the vertices are all coloured.
Count the number of colours used, which is the chromatic number, and answer the question.
The organizers of a music festival must plan the performance schedule for the different groups on the programme, but they have several constraints that must be respected.
The Amateurs cannot play at the same time as The Good-For-Nothings because both groups have the same drummer.
The singer Calvin Harry cannot perform at the same time as Dany Lavoto since both use the same stage equipment.
Calvin Harry and Janis Jackson do not want to perform on stage at the same time since they share the same audience.
The following artists: Calvin Harry, Janis Jackson, Eleanor Rugby, and Dany Lavoto refuse to do their show at the same time as The Brave Penguins because they are too popular and would result in not enough spectators for their own shows.
Finally, Janis Jackson does not want to play at the same time as The Good-For-Nothings because she absolutely wants to attend their show.
In light of all these constraints, what is the minimum number of stages and evening spots that will be necessary to present all these shows during this festival?