Is every acyclic graph 2-colorable?

Every acyclic graph can be transformed structurally to a tree. Therefore, every node on odd numbered levels can be colored with color $X$ and every node on even numbered levels can be colored with color $Y$. Is the reasoning valid?

An acyclic graph, usually known as a forest, is a collection of disjoint trees. It is only a tree if it is connected. Since trees are 2-colorable (for the same reason you mention), it follows that forests are also 2-colorable.

It is also possible to reduce the general case to the connected case: given a forest, you can join the different connected components to form a tree. The resulting tree is 2-colorable, and the same 2-coloring is also valid for the original forest.

StackExchange Computer Science Q#71048, answer score: 2