3.2. Edge Colouring

So, now coming to the edge colouring. Let us see a motivation for studying this problem and then we will discuss the general theory. So, the motivation here is how to schedule a round robin tournament. Imagine you have n teams say n cricket teams representing n countries and again for simplicity assume n to be even but that is not necessary. In a round robin tournament each team has to play against each other. And then based on the results we decide the semi final and then final. So, now we want to schedule the matches, so it is possible to schedule all the matches in 1 single day. So, you will be having n(n−1)/2 number of matches and you may schedule all the matches. In that case each team has to play multiple matches but you do not want to put too much stress on the teams. So, you want to schedule the matches in such a way that no team is forced to play more than a single game on any day. The goal is to come up with a schedule so that you finish all the required matches satisfying this condition in minimum number of days.

The motivation for edge colouring arises from real-life scenarios like scheduling matches in a round robin tournament. In such a tournament, each team competes against every other team. To keep the competition fair and manageable, we need to schedule these matches so that no team plays more than one match in a day. This ensures that players aren't overtaxed and that fans have a better experience watching the matches. An effective way to model this situation mathematically is to represent each team as a vertex and each match between two teams as an edge on a graph. By doing so, we can apply edge colouring principles to help determine how to schedule the matches efficiently.

Think of organizing a sports tournament where teams are represented as people in a meeting. If you schedule all meetings (matches) at once, people may be forced to attend multiple meetings simultaneously. Instead, by assigning meetings to different days (colours), you can ensure each person (team) only attends one meeting per day, making it a lot more feasible and enjoyable.

So, coming to the general problem of edge colouring you are given a graph without loops. The output is an assignment of colour to each edge of the graph so that no two adjacent edges and by adjacent edges I mean who have a common incident vertex. So, I need a colouring of the edges in such a way that no two incident edges are assigned the same colour.

Edge colouring involves assigning colours to the edges of a graph while ensuring that no two adjacent edges, which share a common endpoint, have the same colour. This is a critical concept in graph theory and helps to solve practical problems such as scheduling and resource allocation. Each edge's colour can be thought of as representing a unique time slot or resource assignment, guaranteeing that conflicts do not occur. This problem's formalization allows for better planning and optimization when managing various activities represented as edges in a graph.

Imagine managing a music festival where different bands (edges) perform on overlapping stages (vertices). Each band's performance needs to be scheduled at different times to avoid conflicts. Assigning each performance a different colour ensures that no two adjacent performances—the ones sharing the same stage—occur simultaneously. This keeps the performances organized and the audience happy.

Like vertex chromatic number, we have a related concept called edge chromatic number denoted by χ_0. Edge chromatic number of a graph is the minimum number of colours needed to colour the edges of the graph satisfying this condition that no two adjacent edges are assigned the same colour.

The edge chromatic number, denoted as χ_0, is defined as the smallest number of colours required to colour the edges of a graph such that no two edges incident at the same vertex share the same colour. This concept is crucial for ensuring that edge conflicts are mitigated, especially in practical scenarios like network design and scheduling. Determining this number efficiently is often a challenge, as finding the edge chromatic number for a general graph can be computationally intensive.

Consider a network of roads where intersections (vertices) connect various paths (edges). Each road must be managed to ensure that at any given intersection, no two roads (edges) have the same signal (colour) at the same time. The edge chromatic number tells us how many different signals (colours) we might need to effectively direct traffic without causing gridlock.

Now can we find a lower bound on the edge chromatic number that means what can I say that definitively these many colours are indeed required: it turns out that the lower bound is nothing but the maximum degree of a vertex in the graph. Δ(G) is the maximum degree of a vertex, and how many edges are there? Number of edges is Δ(G) which are incident with the vertex v. So, definitely I need these many colours to colour all the edges incident with vertex v because none of these edges can be assigned the same colours because all of them are incident with a common vertex namely v. Definitely these many colours are required but I may need more than these many colours.

For edge colouring, the lower bound on the edge chromatic number can be established based on the maximum degree (the highest number of edges incident to any single vertex) within the graph. This means that if you have a vertex with degree Δ(G), you need at least that many distinct colours because each edge connected to that vertex cannot share the same colour. However, it is important to note that while this sets a baseline, you might still need more than Δ(G) colours to account for complex interactions in the graph structure.

Think of a manager scheduling meetings with employees (edges) who all report to a single supervisor (vertex). If that supervisor has multiple employees reporting to them (degree), they need to ensure that no two meetings overlap (each represents an edge). Hence, they can't use the same meeting time (colour) for more than one employee. This shows us that they need at least as many time slots as the number of employees, but potentially even more depending on the scheduling conflicts.

There is a theorem called the Gupta-Vizing theorem which says that if you have a simple graph, then you do not need more than Δ(G) + 1 number of colours: this gives a range of values for edge chromatic number the lower bound was the maximum degree and upper bound is 1 plus the maximum degree.

The Gupta-Vizing theorem is a pivotal result in graph theory that provides an upper limit for the edge chromatic number of a graph. It states that for any simple graph, the edge chromatic number will never exceed Δ(G) + 1, where Δ(G) represents the maximum degree of any vertex in the graph. This theorem essentially offers a framework for understanding how colourful (or complex) the interconnections in a graph can be, and it helps to narrow down the possible values for edge chromatic number to a specific range.

Imagine planning a conference with multiple speakers (vertex) who will give presentations (edges) in a single day. The number of presentation slots needed would depend on the number of speakers each presenting unique topics. The Gupta-Vizing theorem acts like a coordinator, telling you that if you can arrange the schedule smartly, you need at maximum one extra slot than the busiest speaker (highest number of topics).

--