Removing vertices that belong to a given set from a graph
Yes, this can be done on an adjacency list representation in $O(|V|+|E|)$ time.  Looping over all the edges can be done in $O(|V|+|E|)$ time.  As you look at an edge, you can check both endpoints; if either one is in $B$, you can delete it.  Afterwards, you can iterate through the vertices and remove the vertices in $B$ (their adjacency lists will be empty, so no need to do anything with their adjacency lists); this takes $O(|V|)$ time.  The entire process takes $O(|V|+|E|)$ time.