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?
$\begingroup$
$\endgroup$
4
-
1$\begingroup$ Yes, the reasoning is valid. As a clarification, every acyclic graph is a tree, no conversion is needed. $\endgroup$– Gabriel TigerströmCommented Mar 2, 2017 at 12:02
-
$\begingroup$ An acyclic graph is a tree iff it is connected. More generally, it is a forest. $\endgroup$– Yuval FilmusCommented Mar 2, 2017 at 13:27
-
$\begingroup$ Valid but not really needed. If your graph has by hypothesis no cycles, it is trivially bipartite. $\endgroup$– quicksortCommented Mar 2, 2017 at 14:02
-
$\begingroup$ "Every acyclic graph can be transformed structurally to a tree." No, every acyclic graph is a tree or a union of trees. That's the definition of tree. $\endgroup$– David RicherbyCommented Mar 2, 2017 at 21:58
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
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.
answered Mar 2, 2017 at 17:57