Question

Construct a coloring of the graph shown using this algorithm.

Short answer

Colour 1 = e, f, d

Colour 2 = a, c, i, g

Colour 3 = b, h, j

Step-by-step solution

Note the given data

Given agraph.

We need to colour the vertex of the given graph using an algorithm.

Definition and Algorithm

A coloring of a simple graph is the assignment of a color to each vertex of the graph so that no two adjacent vertices are assigned the same color.

This algorithm can be used to color a simple graph:

First, list the vertices \({v_1},{v_2},{v_3},......{v_n}\)in order of decreasing degree so that \(\deg ({v_1}) \ge \deg ({v_2}) \ge \deg ({v_3}) \ge ...... \ge \deg ({v_n})\). Assign color 1to \({v_1}\)and to the next vertex in the list not adjacent to \({v_1}\)(if one exists), and successively to each vertex in the list not adjacent to a vertex already assigned color1.Then assign color 2 to the first vertex in the list not already colored. Successively assign color 2 to vertices in the list that have not already been colored and are not adjacent to vertices assigned color 2. If uncolored vertices remain, assign color 3 to the first vertex in the list not yet colored, and use color 3 to successively color those vertices not already colored and not adjacent to vertices assigned to color 3. Continue this process until all vertices are colored.

Calculation

First, we need to list the vertices of the given graph in decreasing order of degree.

Since this ordering is not unique, we will take the vertices as: e( ie \({v_1}\)), a, b, c ,f, h, i, d, g, j

First we assign color 1 to e then the vertices f and d which are not adjacent to e, in that order,

Next we assign color 2 to a, then the vertices c ,i, and g , in that order.

Finally we assign color 3 to b, h and j , in that order.

Thus the algorithm gives a 3-coloring.

Since the graph contain triangles, this is the best possible, so the algorithm is fit here,

Hence solution is

Colour 1 = e, f, d

Colour 2 = a, c ,i , g

Colour 3 = b, h, j