It's been a while since I've done any serous MT programming, so I'm a bit rusty and probably a little behind the times.

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.

Since you probably do have limits on the number of threads you're spawning, you might use a thread pool to control the pace at which the BFS proceeds. For example, the main thread can't continue while there are no threads available.

I think that's the way that I'd start...