Question

Find the edge chromatic number of each of the graphs in

Exercises \(5 - 11\) .

Short answer

This is an exercise of building up the colors and checking that no fewer can be used, since there is no perfect polynomial time algorithm .

We show the minimum chromatic numbers for each exercise below:

Step-by-step solution

The given information

Given ,

The graph of ,

Exercise \(5\) :

Exercise \(6\) :

Exercise \(7\):

Exercise \(8\):

Exercise \(9\):

Exercise \(10\):

Exercise \(11\):

Definition of edge chromatic number  of graph

The edge chromatic number of a graph is the smallest number of colors that can be used in an edge coloring of the graph.

Step 3:Calculation required

Here the number of colors needed to color edges is at least as large as the largest degree of a vertex. Since the edges at each vertex must all be colored differently.

Hence if we can find an edge coloring with that many colors, then we know we have found the answer.

Exercise \(5\) :

In exercise \(5\) there is a vertex of degree \(3\) , so the edge chromatic number is atleast \(3\) .

On the other hand, we can color \(\{ a,c\} and\{ b,d\} \) the same color, so \(3\) colors suffice.

Exercise \(6\) :

In exercise \(6\) the \(6\) edges incident to g must all get different colors. On the other hand , it is not hard to complete a proper edge coloring with only these colors ( for example,color edge \(\{ a,f\} \) with the same color as used on \(\{ d,g\} \) , so the answer is \(6\).

Exercise \(7\):

In exercise \(7\) the answer must be atleast \(3\) ; it is \(3\) since edges that appear as parallel line segments in the picture can have the same color.

Edge chromatic number for exercise \(8,9,10and11\) 

Exercise \(8\):

In exercise \(8\) clearly \(4\) colors are required , since the vertices have degree \(4\) .

In fact \(4\) colors are sufficient . here is one proper \(4\) -coloring ( we denote edges in the obvious shorthand notation):colorfor ac,be,df;color \(2\) for ae,bd,and cf;color \(3\) for ab,cd and ef; and color \(4\)for ad,bf and ce.

Exercise \(9\) :

In exercise \(9\) the answer must be atleast \(3\) ; it is easy to construct a \(3\) -coloring of the edges by inspecting \(\{ a,b\} and\{ c,e\} \) have the same color,\(\{ a,d\} and\{ b,c\} \) have the same color, and \(\{ a,e\} and\{ c,e\} \) have the same color.

Exercise \(10\):

In exercise \(10\) the largest degree is \(6\) ( vertex I has degree \(6\) );therefore at least \(6\) are required.

By trial and error we come up with this coloring using \(6\) colors (we use the obvious shorthand notation for edges); there are many others , of course.

Assign color \(1\) to ag,cd,and hi;color \(2\) to ab,cf,dg,and ei;color \(3\) to bh,cg,di,ef;color\(4\) to ah,ci and de, color\(5\) to bi,ch and fg; and color\(6\) to ai, be and gh.

Exercise \(11\) :

Finally , in exercise \(11\) it is easy to construct an edge – coloring with \(4\) colors;again the edge chromatic number is maximum degree of a vertex.

Despite the appearances of these samples, it is not the case that the edge chromatic number of a graph is always equal to the maximum degree of the vertices in the graph .

The simplest example in which this is not true is \({K_3}\) .

Clearly its edge chromatic number is \(3\) (since all three edges are adjacent to each other ),but its maximum degree is \(2\) .

There is a theorem , however, stating that the edge chromatic number is always equal to either the maximum degree or one more than the maximum degree.