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

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.

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.