1
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.