4
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ Yes, the reasoning is valid. As a clarification, every acyclic graph is a tree, no conversion is needed. $\endgroup$ – Gabriel Tigerström Mar 2 '17 at 12:02
  • $\begingroup$ An acyclic graph is a tree iff it is connected. More generally, it is a forest. $\endgroup$ – Yuval Filmus Mar 2 '17 at 13:27
  • $\begingroup$ Valid but not really needed. If your graph has by hypothesis no cycles, it is trivially bipartite. $\endgroup$ – quicksort Mar 2 '17 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 Richerby Mar 2 '17 at 21:58
2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.