To get the best deal on Tutoring, call 1-855-666-7440 (Toll Free)
Top

Edge Coloring

Edge coloring is one of the types of graph coloring in graph theory, where a combination of colors to the edges of the graph is done, so that no two neighboring edges have the common color.

An edge coloring for a graph G = (V, E) is an assignment φ : E → C such that for any two distinct edges e and f that share an end vertex, φ(e) not equal to φ(f).
Elements of C are called colors. Usually we take C = {1, . . . , c}.

Edge coloring Problem:


The edge-coloring problem is a problem of finding out if it is possible to color the edges of the graph given by using at most c different colors, for a given value of c, or with the least possible colors.
 
The least number of colors sufficient for the edges of a graph given that is known as chromatic number or index of the graph.

For an edge coloring, note that a graph consisting of an even-length cycle can be edge-colored with a set of 2 colors, and odd-length cycles have an edge-chromatic number of 3.

Solving Edge coloring Problem:


By Vizing's theorem, which says, the number of colors needed to edge color a graph is either its maximum degree Δ or Δ + 1.
For few graphs, like bipartite graphs, or high-degree planar graphs, the no. of colors is equal to Δ, and for multi graphs, the number of colors might go to $\frac{3\Delta}{2}$.

No two edges which are on the same vertex can have the same color, in edge coloring.
 
The theorem for edge chromatic index of graphs with 2m vertices for some integer m is as follows:
The edge chromatic index of a graph is given by V(2m) = 2m - 1.
Consider the following figure:

Edge Coloring

Here, V (10) = V (2m) for m = 5, which means 9 colors will be used.

Generalizations:


For a m-regular graph (a graph in which every vertex has m edges), the edge-chromatic index must be either m or m + 1.
Each vertex in V(2m) is of degree 2m - 1, which means that there is an edge coloring with degree 2n - 1. 

 

Edge Coloring Examples

Back to Top

Solved Examples

Question 1: Do the edge coloring of the following graph?
Edge Coloring Examples
Solution:
 
First, we need to set a lower bound which is on the value of the edge of chromatic index, and that is considered to be very simple.
Now as we know that the edge chromatic index of the graph which is given to us is greater than or equal to any vertex's highest degree which is given as 3 in this case.

So with the help of the definition, the edges would be of different colors in edge coloring so that is the incident that occurs on common vertex. Hence if there is any coloring which is in less color than the degree of some vertex of the graph than it must contain two edges with the similar color of that vertex. Hence, the edge coloring will look like this:

Solving Edge Coloring
Here, 1, 2 and 3 represent different colors.
 

Question 2: Do the edge coloring of the following:
Solution:
 

Edge Coloring Example
Hence, for first figure, we will use 3 colors and for the second figure, we will have to use 5 colors.
 


*AP and SAT are registered trademarks of the College Board.