3.2.1. Motivation for Edge Colouring

The problem is that of exam time table scheduling. So, there are n subjects in a college. Imagine there is a college with n subjects; multiple students taking those subjects and we need to schedule the exams for those n subjects in such a way that it should not happen that a student has 2 exams in the same time slot appearing in the schedule.

The issue of scheduling exams is a practical example that many students can relate to. In any college, there are multiple subjects taught, and students enroll in various combinations of these subjects. The challenge arises when exam schedules are created: we must ensure that no student has to take two exams at the same time. This requires careful planning and organization.

Think of it as planning a wedding or a birthday party where multiple guests are invited. You will want to ensure that friends who are in the same friend group are not scheduled for two different parties happening simultaneously. Just like in the student scheduling scenario, proper planning avoids overlaps and conflicts to keep everyone happy.

The n subjects will form the n nodes of my graph. And what will be the edge set so I will add an edge between node number i and node number j which you can interpret as subject number i and subject number j. So, subject number i and subject number j will have an edge among them if there is at least one student who has registered both for the subject i as well as the subject j.

To model this scheduling problem using graph theory, we represent subjects as nodes in a graph. An edge connects two nodes (or subjects) if there is a student who is enrolled in both subjects. This means that if there's an edge between two subjects, those exams cannot be scheduled at the same time since at least one student has an overlap.

Imagine organizing a dinner party where different guests cannot be at the same table due to personal conflicts. If guests A and B cannot sit at the same table (like subjects with an edge), you need to arrange seating such that no conflicting guests are placed together, similar to scheduling the exams.

I will be interested to colour the nodes of the graph by various colours. And my colouring should satisfy the condition that no two adjacent nodes should get the same colour. And the number of time slots or minimum number of time slots I require is the same as the minimum number of colours needed to colour the vertices.

In graph coloring, each node (subject) can be colored differently to represent different time slots for exams. The rule is that adjacent nodes (subjects that cannot be scheduled simultaneously due to overlapping students) must be colored differently. Thus, the minimum number of colors represents the fewest time slots needed to schedule all the exams without conflicts.

Imagine a painter working on a mural. They can only use a certain color for certain sections that are adjacent to one another; if two sections touch, they have to be different colors to prevent clashing. This is akin to ensuring that exams that cannot happen at the same time are scheduled in different time slots.

Of course a trivial way to colour the vertices will you take n distinct colours and assign one distinct colour to each of the n vertices. I do not want to do that but because that is equivalent to saying that I conduct exams for the n subjects taking n slots.

To maximize efficiency, we want to use fewer colors than the total number of subjects, which corresponds to minimizing time slots for exams. Assigning each subject a unique color would mean scheduling each exam in a separate time slot, leading to unnecessary resource expenditure. Therefore, our goal is to find the minimum number of colors needed, which correspond to scheduling the fewest exam slots without conflicts.

Think of coordinating multiple sales at a local market. If each stall (representing a subject) has to operate in its own time frame without overlap, you would have many separate events. Instead, you'd want to group similar items together on some days to reduce the number of market days needed—this is similar to how we want to minimize the number of colors in our graph.

This algorithm is based on the greedy strategy which is a very popular strategy in algorithm designs. So, what exactly is the greedy strategy here: the greedy strategy is that you use the first available colour at every step if possible, if not possible then use a new colour.

The greedy algorithm is a practical approach to efficiently color the graph where in each iteration you assign a color to an uncolored vertex by picking the first color that is not used by its adjacent (already colored) vertices. It's a straightforward method, though it may not always yield the optimal solution.

Imagine you're doing laundry and sorting colored clothes. You might first choose the color that has more clothes in it to avoid overwhelming sorting errors. If one color is too common (already used), you simply pick the next available color—this mimics the greedy algorithm where you make the best choice available at each step.

--