Let $G=(V,E)$ and denote $d=d(G)$ its maximal degree and $a=a(G)$ its arboricity. My question is: what is the smallest amount of colors $f(a)$, such that a $f(a)$-coloring is guarenteed to exist?
For example, $f(d)=d+1$, because a $d+1$-coloring always exists.
My assumption is that $f(a)=2a$. Because each forest can be colored by $2$ colors (Am I correct?), and by using unique color palleteus, we get a $2a$-coloring.
I would like to ask:
- Is my explanation correct?
- Is there a smaller function (depending only on $a$)?