find chromatic number

127 Views Asked by At

I came across this problem in my textbook.(problem no: 3)
enter image description here

I created a graph with students as vertices and if two students took same course,then there is an edge between them.
But I ended up getting this graph
enter image description here

I'm not sure how to proceed further.

1

There are 1 best solutions below

1
On BEST ANSWER

I suppose you want to interpret the question as one about the chromatic number of a graph. This means that you assign colours to vertices. Here, colours should be time slots (whose number you want to minimize), and the vertices have to be things that get assigned a time slot, i.e., rhe vertices are the courses. Also, edges shall represent obstacles to assigning the same time slot (=colour) to distinct courses (=vertices). Hence we join courses by edges whenever they have a student in common. So e.g. Linda gives rise to an edge $AT$, and Abe gives rise to three edges $CF$, $CT$, and $FT$.