Your solution looks good to me!
I have one suggestion if you consider directed graphs. Consider the graph:
A -> B -> C
D -> F
Let's say your algorithm starts arbitrarily at node B. It will traverse the graph through B and C and mark them as connected components - but it won't catch A!
A simple way to solve this problem is to allow the DFS to traverse the graph going both forwards and backwards, as though the graph was non-directed.
This is another way to solve it: Your algorithm produces sets of connected components. Let's say, as above, that the algorithm starts at B and produces the set {B, C}. Then, let's say that the algorithm arbitrarily selects A as its next starting point. When it traverses the graph to B, it should union the new set of connected components {A} with the already-existing set {B, C} instead of simply skipping node B.
In general, if you encounter a node that's already part of a group of connected components during a DFS, mark the set of connected components that the node is in and then skip the node. Then, when you've finished traversing as many nodes as possible without retracing paths found by previous DFS's, union all of the marked sets and the set produced by the most recent DFS into one set of connected components and discard the unioned sets.
I have the answer for c = 1/2.
Just consider the white edges. As you might know, for every (undirected) graph you can can delete at most half of edges to get a bipartite graph. We'll call the partitions A and B. So there are at least half of the white edges between the group A and B. So if we color all the vertices of which ever group to white, there are at least half of the white edges which is connected to at least one white vertex. So we can choose to paint all the vertices of A to white, or all the vertices of B to white. (We'll choose it later)
Now that we partitioned the vertices into two groups, we want to see which partition should we paint to black, the other partition would be colored to white, and as mentioned, for whites the conditions is held.
The black edges between two partitions, will be connected to at least one black vertex whichever way. Now see the black edges inside the partitions. If black edges in partition A is more, we'll color all the vertices of the A to black. And if black edges in partition B is more, we'll do otherwise.
You can see for white and black the conditions is held.
Proof for the theorem used in this solution: Given a graph, partition it into 2 groups whichever way. If there was a vertex in one group, which more than half of its neighbors are in its group, move the vertex to the other partition. You can see this operation will end, and when ended, for each vertex at least half of its neighbors is in the other group. So at least half of the edges is in-between the partitions.
Update: In this proof, by neighbors we mean the number of edges connected to one vertex.
Best Answer
This problem is equivalent to finding a maximal independent set and colouring it white. To solve it, depth-first search on the graph, and colour the source node white.
If the graph is directed, change it to an undirected graph by replacing every edge with an undirected edge.
To clarify the terminology, "no two white colors are adjacent" means if 2 white vertices are connected by a directed edge, it violates this condition, so here the edge behaves as it is undirected. Since "between the white node and the black node there exists one directed path of length at most 2", so if there is an edge from the white node to the black node, it satisfies this criteria. Since "for each black node there exist at least one white node which is adjacent to it", if there is an edge from the black node to the white node, this criteria is also satisfied.
Let $x$ be the current node in the depth-first search.
If any of $x$'s neighbours has been coloured white, colour $x$ black. Otherwise, colour $x$ white.
Checking $x$'s neighbours can be done in $O(E)$ time for the entire graph over the depth first search, hence the entire algorithm is $O(V+E)$ time if the graph is stored as an adjacency list.
This algorithm terminates. We now show it works. If a node is coloured black, then some neighbour has to be white so that it can be coloured black.
Otherwise, a node is coloured white. The visited neighbours of the node (when the node is visited) are black. The subsequent unvisited neighbours of the nodes will not be coloured white as they are adjacent to a node that is coloured white. Hence all neighbours will be coloured black.
Hence, this satisfies your condition.