Would you like to know if you can use the coloring technique in targeted graphs? If yes or no, why?
Would you like to know if you can use the coloring technique in targeted graphs? If yes or no, why?
Yes, but note that if there is an edge A → B, then A and B must have different colors, otherwise A would have a neighbor (B) with the same color. The same reasoning holds, but on the contrary, if the edge is B → A. Coloring a directed graph is not different from coloring an unguided graph; so no one distinguishes the two cases.
This is different from what happens in the problem of finding the minimum generating tree: consider the graph below.
If the graph was not directed, the smallest minimum generating tree (in the sense that it is the minimum weight subgraph where there is always a path between any two vertices) would obviously be composed of the edges A - B and B - C. p>
Since it is the graph is directed, however, this minimum weight subgraph is the tree minimum generating, which, in this case, has to have the three edges A → B, B → C, C → A; for this other problem, the graph is directed or does not make a difference.