On a coloring that uses $2\cdot a\left( G \right)$ colors

Question

Denote $G=\left( V, E \right)$ arboricity by $a\left( G \right)$. I'm trying to understand why $G$ is $2\cdot a \left( G \right)$-colorable. I came across this post. Both the OP and the answer say that $E$ can be partitioned to $F_1 , ..., F_a$. Then, color $V_1$ is $2$ colors because its a forest. then, color $V_2 \backslash V_1$ in $2$ new colors because this is still a forest, and so on.

I agree that the amount of colors to be used will be $2\cdot a \left( G \right)$. What bothers me, is that each coloring of a single forest is proper when you look at the forest itself, but might not be proper once you look at the entire graph.

Let me give a partial example. Say we have $\left( u_1 , u_2 \right), \left( u_2 , u_3 \right), \left( u_1 , u_3 \right)$, and say $\left( u_1 , u_2 \right), \left( u_2 , u_3 \right) \in F_1$ and that $\left( u_1 , u_3 \right) \in F_2$. So $u_1,u_2,u_3$ are spanned by $F_1$. Hence, they will be colored in $2$ colors: $1$ and $2$. WLOG, $f\left( u_1 \right) = 1$, $f\left( u_2 \right) = 2$, $f\left( u_3 \right) = 1$. Now as we approach $F_2$, the vertices $u_1,u_2,u_3 \notin V_2 \backslash V_1$. therefore their color will not be altered.

So, the coloring was proper when our world was $F_1$. However, upon looking at the entire graph, our coloring is not proper, and that's what bothers me.

Answer 1

The proof given in the linked post is wrong. Here is a correct proof, taken from Steven Butler's notes.

A forest of $k$ trees on $n$ vertices contains $n-k$ edges, and so its average degree is $\frac{2(n-k)}{n} < 2$. Therefore, if a graph has arboricity $a(G)$, then its average degree is less than $2a(G)$. Consequently, a graph of arboricity $a(G)$ always contains a vertex of degree at most $2a(G) - 1$.

Given a graph $G$ of arboricity $a(G)$, we arrange its vertices in order $v_1,\ldots,v_n$ as follows. The first vertex $v_1$ is an arbitrary vertex of degree at most $2a(G) - 1$. Now remove $v_1$ from the graph. The resulting graph still has arboricity at most $a(G)$, so it ontains some vertex $v_2$ of degree at most $2a(G) - 1$. Remove $v_2$ from the graph, and repeat.

We have ordered the vertices in such a way that $v_i$ has at most $2a(G) - 1$ neighbors in the subgraph of $G$ induced by the vertex set $\{v_i,\ldots,v_n\}$. This allows us to greedily color $G$ using $2a(G)$ colors: scanning the vertices in reverse order $v_n,\ldots,v_1$, each vertex $v_i$ has at most $2a(G) - 1$ neighbors which have already been colored (since at this point, only the vertices $v_{i+1},\ldots,v_n$ have been colored), and so we can always color it using some color in $[2a(G)]$ without creating a monochromatic edge. After processing all vertices in this way, we obtain a valid coloring of the entire graph using at most $2a(G)$ colors.