3.1.2. Vertex Colouring Problem

So, let us start with vertex colouring first and let us see some real world motivation for studying the vertex colouring problem; 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 and we need to schedule the exams in such a way that it should not happen that a student has 2 exams in the same time slot appearing in the schedule.

Vertex colouring is a method used in graph theory and practical applications to assign colors (or time slots, in this case) to vertices (or subjects) such that no two adjacent vertices (or subjects taken by the same student) share the same color. In an exam schedule, for instance, if a student takes multiple subjects, their exams must not overlap in timing. The goal is to minimize the number of time slots needed for this scheduling which reflects on the concept of vertex colouring.

Imagine you are organizing a concert where different bands perform at different times. Each band represents a node, and every student who likes both bands represents an edge connecting those two nodes. To ensure that no student has to choose between two bands, you must schedule them in different time slots. The challenge is to do so using the least number of time slots possible, similar to using the least number of colors in a graph.

Instead we would require or we would be interested to find out the minimum number of time slots where I can allow multiple exams to be conducted in the same time slot, but without violating the condition that no student has two exams in the same time slot. It should not happen that I schedule the exams in such a way that a student who has taken two subjects and both the subjects appear in the same time slot in my schedule that should not happen.

To find a solution to the scheduling problem, we can represent the subjects and their relationships in a graph. Each subject becomes a vertex (or node) in the graph and an edge is created between any two subjects for which at least one student is taking both. If a student is taking two subjects, those subjects cannot share a time slot, indicating they cannot be the same color in the graph. Thus, the problem can be transformed into a vertex coloring problem.

Think of a social network where nodes are people and edges show connections based on friendships. If two people are friends, they cannot attend the same event at the same time. Therefore, to plan the events (color the graph), we must ensure no two friends (connected nodes) are at the same event (share the same color).

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.

The vertex chromatic number, denoted χ(G), is defined as the smallest number of colors needed to color the vertices of a graph such that no two adjacent vertices share the same color. This chromatic number directly relates to our problem; the less colors needed, the fewer time slots required for exams. This reflects an efficient scheduling approach that avoids conflicts.

Consider a painter trying to paint an intricate design on a wall. Each section of the wall should not have the same color touching its neighboring section. Finding out the minimum distinct colors needed for this design reflects the concept of a chromatic number in graph theory.

It turns out that finding the chromatic number of a graph is indeed a hard problem. Hard problem in the sense we do not have in general efficient algorithms or practical algorithms for finding out the vertex chromatic number of a graph, if the number of vertices n in the graph is arbitrarily large or very large.

Determining the vertex chromatic number can be computationally challenging, especially for large graphs. This complexity arises because the arrangements and relationships in the graph can increase exponentially, making it difficult to compute the minimum coloring effectively. The task of finding algorithms that efficiently determine this chromatic number remains an area of active research and interest in the field of graph theory.

Imagine trying to solve a massive jigsaw puzzle. As the puzzle grows larger, the pieces become increasingly complex to fit together correctly. Finding the optimal arrangement without some advanced strategies becomes impractical, much like finding the minimum number of colors needed in a large graph.

It turns out that the vertex chromatic number of a graph is always upper bounded by 1 + the maximum degree of any vertex in your graph.

The maximum degree of a vertex in a graph is the largest number of edges connected to a single vertex. The vertex chromatic number cannot exceed this maximum degree plus one since, in the worst-case scenario, a vertex might need to be assigned a different color than all its adjacent vertices. This gives us a bound to help understand and navigate the coloring problem more easily.

Think of a group project where one student has connections to their peers (like friendships). If they need to collaborate with everyone else, they can’t share the same ideas simultaneously. The maximum number of connections (friendships) they have (degree) determines how many different ideas (colors) they might need to cover all possibilities effectively.

So, 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 coloring algorithm approaches the vertex coloring problem by iteratively assigning the lowest numbered color that is allowable based on previously assigned colors of adjacent vertices. This strategy aims to minimize the number of colors used while ensuring that no two adjacent vertices share the same color. However, it may not always yield the optimal solution.

Consider a student trying to group subjects for their study sessions. They pick one slot (color) and see what other slots (colors) are already chosen by their friends (adjacent vertices). If a slot is taken, they quickly choose another one (the first available), hoping to finish the scheduling efficiently.

So, the question is will this algorithm always give the optimal colouring and what do I mean by optimal colouring? By optimal colouring I mean the minimum number of colours that is indeed required to colour all the vertices of my graph namely the number of colours is exactly the vertex chromatic number. So, it turns out that this algorithm may not always give you the optimal colouring because it depends upon the sequence in which you pick the uncoloured vertices in every iteration.

The efficiency of the greedy algorithm hinges significantly on the order of vertex selection. Depending on which vertex is colored first and the subsequent choices made, the final count of colors could vary widely. This means that while a greedy approach provides a good approximation, it cannot guarantee the optimal solution in all cases.

Think of filling out a survey. If you randomly fill out questions without thinking about how they connect, you may not provide the best responses (colors) possible. However, if you pay careful attention to the previous answers, you might enhance the overall quality of your survey.

Let me demonstrate my point here so imagine this is a graph given to you and we want to assign colours to the vertices by following this algorithm. So, if I follow the vertex ordering {v , v , v , v , v , v } then I will need 4 colours why so? ... So, definitely 2 is the minimum number of colours needed to colour all the vertices of this graph.

By examining different sequences in which vertices can be colored, it becomes evident that the order can affect the overall coloring outcome. In the example provided within the text, different colorings yield varying results based on the vertex selection order, illustrating that sometimes judicious choices lead to optimal outcomes, while other orders can result in unnecessary excess.

Consider packing for a trip. If you organize your clothes in one order that considers needing certain items first, you might fit everything efficiently into your luggage. However, if you randomly toss items in without strategy, you may find yourself needing to leave behind essentials (causing an inefficient use of space).

So this algorithm guarantees that you do not need more than maximum degree plus 1 number of edges ... This gives a formal understanding of why the greedy algorithm remains bounded by the maximum degree plus one, implying that it's a reliable, though not flawless, approach.

The greedy approach, while not always optimal, ensures that the color count remains within a manageable range—no more than the maximum degree of any vertex plus one. This property helps to simplify the problem by providing a safeguard against excessive colors, allowing us to work efficiently within known bounds.

Think of meal planning for a week. While you might have some flexibility in choices (colors), you want to ensure you don’t exceed the available ingredients (maximum degree). Therefore, planning with a maximum number in mind keeps things efficient and practical.

--