I have an undirected graph $G=(V,E)$ and I want to find an ordering of $V$, $\pi=(v_1, v_2, ..., v_n)$, such that for each $1 \leq i \leq n$, $v_i$ is of minimum degree in the subgraph $G_i = [\{v_1, ..., v_{i-1}, v_i\}]_G$ in $O(n+m)$ time, where $n=|V|$ and $m=|E|$. I also have to prove that if $G$ is a tree, then a greedy coloring algorithm that colors the nodes in the order they are found in $\pi$ will always use at most 2 colors.

My idea was to first compute the degree of each node in the graph (which can be done in $O(m)$), store the values in an array, then sort that array in descending order using an $O(n)$ sorting algorithm like Counting Sort or Radix Sort. However, it seems this approach isn't entirely correct, as I found a counterexample for which the coloring algorithm has to use 3 colors. So if this isn't the way to go about it, how can I find $\pi$ in $O(n+m)$?

  • $\begingroup$ Is this a homework problem? $\endgroup$ Dec 22 '21 at 7:07
  • $\begingroup$ Hint: Vertex with the minimum degree in $G$ is the last vertex in the ordering. Do this process inductively. $\endgroup$ Dec 22 '21 at 7:08

Your Answer

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

Browse other questions tagged or ask your own question.