3. Vertex and Edge Colouring

Hello everyone, welcome to this lecture; the plan for this lecture is as following. We will discuss about vertex colourings, vertex chromatic number and we will discuss about edge colouring and edge chromatic number.

This introductory chunk sets the stage for the lecture. The speaker outlines the main topics that will be covered: vertex colourings, vertex chromatic numbers, edge colouring, and edge chromatic numbers. Each of these topics revolves around the concept of assigning colours to graph nodes or edges without violating specific rules.

Imagine planning a schedule where different classes occur in a school. Each class represents a vertex, and the rule is that no two classes with a common student can happen at the same time (i.e., they can't have the same colour). This situation parallels the concepts in this lecture.

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...

The application of vertex colouring is illustrated with the example of scheduling exams for multiple subjects in a college. The goal is to avoid scheduling two exams at the same time for a student enrolled in both. The subjects are represented as graph vertices, and edges connect vertices if a student is registered for both subjects. The task is to colour these vertices (assign time slots) so that no two connected vertices share the same colour (exams at the same time).

Consider planning a family gathering with several relatives. If each relative can only attend one event at a time, you need to plan events (exams) without overlapping attendees (students) in the same time slots (colours).

So, how do we model this problem as a graph theoretic problem? So, the n subjects will form the n nodes of my graph...

This chunk explains how to model the exam scheduling problem using graph theory. Each subject is a vertex, and edges are drawn between subjects that have at least one student in common. Therefore, if there's an edge connecting two vertices, those subjects cannot be scheduled at the same time. The objective is to find the smallest number of colours needed to colour the graph such that no two adjacent vertices (subjects with a common student) share the same colour.

Think of each subject as a sports event, and an edge as a situation where two events have participants from the same team. If events are connected by an edge, they cannot occur at the same time, just like scheduling sports games without forcing team members to choose between games.

What is the vertex chromatic number of a graph? ... the vertex chromatic number is the minimum number of colours needed to colour the vertices...

This section clarifies the definition of the vertex chromatic number (χ(G)), which indicates the minimum number of colours required to colour the vertices of a graph so that no two adjacent vertices share the same colour. This concept is critical in applications that require optimal scheduling or allocation but can be computationally complex to determine for large graphs.

Imagine you are organising a painting class. The chromatic number helps you determine the fewest paint colours you need to arrange different projects (vertices) without duplicates for connected projects (adjacent vertices).

It turns out that finding the chromatic number of a graph is indeed a hard problem...

The lecturer discusses the complexity of determining the vertex chromatic number for large graphs. While it's possible to calculate chromatic numbers using exhaustive methods, these are not efficient for large graphs because the number of vertices can increase rapidly. The discussion highlights a computational challenge in graph theory.

Consider a large-scale university with numerous courses and student registrations. Finding an ideal schedule would require massive computational effort to ensure no scheduling conflicts, demonstrating how complex the chromatic number can be to ascertain.

So, this algorithm is based on the greedy strategy which is a very popular strategy in algorithm designs...

The greedy algorithm assigns colours to the vertices sequentially, choosing the first available colour that does not violate the colouring rules. This is done in iterations, where each uncoloured vertex is considered, and the set of used colours is updated. The algorithm continues until all vertices are coloured, but it does not always produce the optimal colouring.

Imagine picking outfits for a week where the goal is to not repeat combinations; a greedy approach would mean selecting the first available outfit. If you encounter an overlap (a meeting in the same outfit), you must switch, demonstrating how the simplicity of greedy methods can lead to suboptimal outcomes.

So, now the question is will this algorithm always give the optimal colouring...

This chunk addresses whether the greedy algorithm yields the optimal colouring for all scenarios. The lecturer provides examples showing that depending on the order of vertex selection, the algorithm might need more or fewer colours. It emphasizes the non-uniqueness of greedy decisions based on vertex selection order.

Think about arranging a concert with different acts. If you start with a popular band, scheduling the lesser-known bands afterward might lead to conflicts, just as choosing vertices in a specific order can alter the outcome of colour assignments.

So, now let us see a related concept which is called as edge colouring...

This section introduces edge colouring as a counterpart to vertex colouring, focusing on assigning colours to the edges of a graph instead of the vertices. The objective here is to ensure that no two adjacent edges (edges sharing a vertex) receive the same colour, analogous to scheduling events or matches without overlaps. The concept is vital in scenarios such as round robin tournaments.

Consider planning a sports league: teams playing against each other form edges on a graph. Each colour represents a day of matches, ensuring no team plays more than once each day maximizes scheduling efficiency.

And we want to output an assignment of colour to the each edges of the graph so that no two adjacent edges...

The edge chromatic number (χ₀) is defined as the minimum number of colours needed to colour the edges of a graph without sharing colours on adjacent edges. This concept is as complex as vertex colouring and retains similar challenges when attempting to identify its value for larger graphs.

Continuing with the sports analogy, when scheduling games, you want to ensure that no two matches using the same field (adjacent edges) occur at once. The edge chromatic number would help minimize the number of game days while maximizing play.

Now can we find a lower bound on the edge chromatic number that means what can I say that definitively these many colours...

The lecturer discusses the bounds of the edge chromatic number, establishing its lower bound as the maximum vertex degree (Δ(G)) of any vertex in the graph. The upper bound follows from Vizing's theorem, stating that the edge chromatic number cannot exceed Δ(G) + 1. The actual value can vary widely between those bounds, reflecting the inherent complexity of edge colouring.

In our sports league scenario, if a team has many games scheduled on the same day (high degree), you need at least that many different colours (preparations of days) for scheduling while acknowledging that sometimes fewer might suffice.

So, these are the references for today’s lecture. And with that I conclude today's lecture; just to summarize in this lecture we introduced the problems of vertex colouring...

In this conclusion, the main topics of the lecture are revisited. Vertex colouring and edge colouring were discussed alongside the chromatic numbers associated with each concept. The challenges of finding optimal solutions and the greedy algorithm's behaviors also summarized the session's learning points.

Just as a conference organizer must reflect on learned tactics from different presentations to improve future scheduling, students can apply what they grasped in this lecture to potential real-world applications they will face in careers.

--