4
I would like to know if it is possible to use the staining technique in directed graphs? Whether yes or no, why?
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 true, but on the contrary, if the edge is B A. Coloring a directed graph is no different than coloring an undirected graph; therefore nobody distinguishes the two cases.
This is different from e.g. in the problem of finding the minimum generating tree: consider the graph below.
If the graph were not directed, the smallest minimum generating tree (in the sense of being 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.
Since the graph is directed, however, this minimum weight subgraph is a arborescence minimum generator, which in this case has to have the three edges A B, B C, C A; for this other problem, the graph being directed or not makes, yes, difference.
Browser other questions tagged graph
You are not signed in. Login or sign up in order to post.
I understood, my question was precisely because nobody distinguishes the two cases, thank you!
– William Pereira
but and coloring of vertices and faces, it is also possible?
– William Pereira
Coloring faces is equivalent to coloring the vertices of the dual graph (and then again worth the above answer).
– user25930
"Arborescence"?
– Jefferson Quesado