Use a greedylist coloring with vertex order 1 3 8 6 2 5 4 9

Use a greedy/list coloring with vertex order {1, 3, 8, 6, 2, 5, 4, 9, 10, 7} to color the graph below. Label the vertices with the appropriate color/color number or simply list the vertices and their corresponding colors True or false. If the statement is false, provide a specific counterexample using a graph of order at most 5. Any greedy/list coloring of any bipartite graph will always produce an optimal 2 coloring. Any greedy list coloring of any tripartite graph will always produce an optimal 3- coloring.

Solution

1.Choose an order for the vertices. i.e.{1,3,8,6,2,5,4,9,10,7}
Choose a list of colors, also in some order.
Let
Color #1 is blue
Color #2 is red
Color #3 is green
Color #4 is orange

In order, color each vertex using the first legal color on the list, making sure that no two adjacent vertices are the same color.
Continue in this way until each vertex is colored.
In order, we color each vertex with the lowest numbered color we can,following the coloring rules

1.Start with vertex1,say colour it with color#1 (Blue);(v1,Blue)
2.Vertex 3 : Since V3 doesn’t border any vertices we have not colored yet, it can also be blue also i.e (v3,Blue)
3.V8:Since V8 has border V3 colored Blue,select second color in list i.e Red (v8,Red)
4.V6:v6 has border v1 colored blue and V8 colored red,select 3rd color in list i.e Green(v6,Green)
5.V2:has border V1 colored Blue and and v3 colored blue,we can add Red(next lowest color in list)i.e(v2,Red)
6.V5:has border v1 colored blue ,so we can add Red.i.e(v5,Red)
7.V4:has border v5 with Red and v3 with blue,so color with Green(v4,Green)
8.V9:has border v4 green ,v6 green color with Blue(lowest color in list)i.e(v9,Blue)
9.V10:has border v5 with Red and v8 Red,color with Blue (v10,Blue)
10.V7:has borders v2 Red,v10 Blue and v9 Blue,color with Green .i.e(v7,Green).

So 3 colors are used.