For the sake of argument, let's say your nor using a thread pool and don't have any limits on the number of threads you can spawn. You could associate a condition variable with each vertex using a property map, and make that available to your BFS visitor. By overriding on_tree_edge, you can get access to the parent/child vertices in the BFS tree. Your child vertex can spawn a new thread and wait on the condition variable associated with the parent. IIRC this means that you can have multiple children waiting on the parent. When the parent thread is done, it notifies the condition variable, waking up all of its dependant children. Of course, children wouldn't have to wait if the parent had already finished, so you'll probably want to make sure that there's a valid and initialized condition variable before waiting on it.
Thank you for the tips, Andrew. What about the case where we have a child waiting on multiple parents? That seems like a bit more difficult case...? James