Is it possible to use coloring of vertices, edges or faces in a DIRECTED graph?

4

Would you like to know if you can use the coloring technique in targeted graphs? If yes or no, why?

    
asked by anonymous 05.06.2015 / 14:32

1 answer

2

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.

    
05.06.2015 / 14:42