Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It only takes a minute to sign up.
Sign up to join this community
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.
