I'm learning about the greedy algorithm, but this question is to general for me to grasp (I ave no idea where to begin). Could someone please explain how I solve the problem?
Show that for any graph $G$ there is an ordering of the vertices for which the greedy algorithm requires $χ(G)$ colors.
Start with a coloring with $\chi(G)$ colors. Put all the vertices in color class $1$ at the start of the ordering. The greedy algorithm with color them all with color $1$. Put the vertices in color class $2$ next in the ordering. The greedy algorithm will color them all with color $1$ or $2$. It will not color them all with color $1$ though. (Why not?) Continue in this fashion.