3.2.3. Lower and Upper Bound on Edge Chromatic Number

So, now coming to the general problem of edge colouring you are given a graph without loops. And what we want here as an output? We want to output an assignment of colour to the each edges of the graph so that no two adjacent edges and by adjacent edges I mean who have 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 chromatic number, denoted as χ₀(G), focuses on coloring the edges of a graph rather than the vertices. The primary goal is to ensure that no two edges that share a common vertex receive the same color. This requirement is similar to vertex coloring but involves edges and their relationships.

Imagine scheduling matches in a sports league where each match is an edge. If two matches are scheduled at the same time and involve the same team (the vertex), they cannot have the same color. Hence, each match (edge) must be colored uniquely if they share a team (vertex), ensuring no team plays more than one match at the same time.

And again like vertex colouring, finding the edge chromatic number of an arbitrary graph with large number of vertices is a hard problem, you do not have efficient algorithms or practical time algorithms for finding the minimum number of colours. Of course you can do a brute force and try to see whether 1 colour is sufficient, 2 colour is sufficiently, 3 colour is sufficient, 4 colour is sufficient, 5 colour sufficient. And then you will hit upon the right answer but that will require you enormous amount of time so that is not an efficient algorithm. 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 you take the vertex which has the maximum degree say the vertex v has the maximum degree. So, I have the vertex v and it has the maximum degree and how many edges are there? Δ(G) number of edges are incident with the vertex v. So, definitely I need these many number of colours to colour all the edges incident with the 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 number of colours are required but I may need more than these many colours as well.

The lower bound for edge chromatic number is determined by the maximum degree of the graph, denoted as Δ(G). This means that if a vertex has a maximum degree of 'd', you will need at least 'd' colors to color the edges connected to that vertex. This is because each edge incident to this vertex cannot share a color with another edge that hits the same vertex. It's important to note that while this sets a minimum requirement, the actual number of colors needed could be higher depending on the graph's structure.

Think of a wheel with spokes. If the hub (center) of the wheel connects 5 spokes (edges) to the outer rim, each spoke must be a different color. So, you need at least 5 colors here to avoid any two spokes touching the same hub having the same color. However, if the wheel has more complex connections, you might end up needing more than 5 colors.

And what can I say about upper bound so there is a very interesting theorem called as the Gupta-Vizing theorem which says that if you have a simple graph then you do not need more than these many number of colours: Δ(G) + 1. So, basically we get 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 upper bound for edge chromatic number is expressed by a theorem known as the Gupta-Vizing theorem, which states that the edge chromatic number of a simple graph will not exceed Δ(G) + 1. In simple terms, while you need at least Δ(G) colors to meet the lower bound requirement, you should never need more than one additional color beyond that. This theorem provides a reliable framework for estimating how many colors are necessary for edge coloring in various graph configurations.

Imagine organizing a large conference with different sessions (edges). If the maximum number of attendees in any session is 5 (Δ(G)), you can effectively manage them using 6 different rooms (colors). This means that while you can run five sessions in their own rooms, that sixth room gives you flexibility to accommodate other sessions without conflicts in scheduling.

--