# Showing a coloring for a graph

How would I do A,B,and C fo the following graph.

A. For A I used the greedy algorith. So I did $v_1=1,v_2=1,v_3=1,v_4=1,v_5=2,v_6=2,v_7=3,v_8=4$

So I got that the chromatic coloring is 4.

C. For C I said no because we know for every graph G the chromatic number will always be less than or equal to 1 plus the the largest degree in the graph and $1+\Delta=4$ so there cannot be a coloring with more than four colors using greedy.

B. I think there is a different ordering using different ordering that uses fewer color but I canot find it.

• the problem with the ordering is, that for node $v_8$, all three nodes around it already are coloured in a different colour. Try to find an ordering where this does not happen Nov 21, 2017 at 23:17
• you should be able to get an ordering using only 2 colours (as this is a tree) Nov 21, 2017 at 23:18
• your answers to a and c look good for me :) Nov 21, 2017 at 23:19

Intuition says if you do it bad then do it conversely. :-) The greedy algorithm directed by the inverse order $v_8,\dots, v_1$ produces a two-color coloring.