Question

Use pseudocode to describe this coloring algorithm.

Short answer

coloring G: simple graph with vertices \({v_1},{v_2},{v_3},......{v_n}\)where\(n \ge 1\)

\({v_1},{v_2},{v_3},......{v_n}: = \)The vertices\({v_1},{v_2},{v_3},......{v_n}\)ordered in decreasing order of degrees.

count: = 0

color: = 1

fori: = 1to nc(i) : =0

\(A\left( {color} \right) = \phi \)then

while count <n

fori: = 1to n

if c(i) =0 and

\(A\left( {color} \right) = \phi \)then

c(i): = color

\(A\left( {color} \right): = A\left( {color} \right) \cup \left\{ i \right\}\)

count: =count +1

if c(i) =0 and

\(A\left( {color} \right) = \phi \)then ifthere is no edge\(\left\{ {{v_1},{v_2}} \right\}\)for all j in\(A\left( {color} \right)\)then

c(i): = color

\(A\left( {color} \right): = A\left( {color} \right) \cup \left\{ i \right\}\)

count: =count +1

\(A\left( {color} \right): = A\left( {color} \right) \cup \left\{ i \right\}\)

count: =count +1

\(A\left( {color} \right) = \phi \)

returnc(1), c(2),…..c(n)

Step-by-step solution

Note the given data

Given the ordered vertex set \({v_1},{v_2},{v_3},......{v_n}\) with \(\deg ({v_1}) \ge \deg ({v_2}) \ge \deg ({v_3}) \ge ...... \ge \deg ({v_n})\)

We need to use of pseudocode to describe the coloring algorithm.

Algorithm

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.

Pseudocode procedure and calculation

coloring G: simple graph with vertices \({v_1},{v_2},{v_3},......{v_n}\) where \(n \ge 1\)

\({v_1},{v_2},{v_3},......{v_n}: = \)The vertices\({v_1},{v_2},{v_3},......{v_n}\)ordered in decreasing order of degrees.

count: = 0

color: = 1

fori: = 1to nc(i) : =0

\(A\left( {color} \right) = \phi \)then

while count <n

fori: = 1to n

if c(i) =0 and

\(A\left( {color} \right) = \phi \)then

c(i): = color

\(A\left( {color} \right): = A\left( {color} \right) \cup \left\{ i \right\}\)

count: =count +1

if c(i) =0 and

\(A\left( {color} \right) = \phi \) then ifthere is no edge\(\left\{ {{v_1},{v_2}} \right\}\)for all j in\(A\left( {color} \right)\)then

c(i): = color

\(A\left( {color} \right): = A\left( {color} \right) \cup \left\{ i \right\}\)

count: =count +1

\(A\left( {color} \right): = A\left( {color} \right) \cup \left\{ i \right\}\)

count: =count +1

\(A\left( {color} \right) = \phi \)

returnc(1), c(2),…..c(n)

which is the required solution.