The watershed partition of an image often results in over-segmentation. This well-known phenomenon is due to variations of intensity that do not correspond to object boundaries and produce spurious local minima in the image gradient magnitude. Filtering minima or merging watershed regions is then necessary to obtain a higher-level description of the data. In this paper, we propose new solutions to this problem by applying two interactive multilabel partitioning techniques to the adjacency graph of the watershed regions. In our first approach, the partition is derived from the probability that a "random walker" starting at an arbitrary node, first reaches a node with a pre-assigned label. In the second approach, we compute a geodesic partition of the graph using competing wavefronts starting at prescribed nodes. Both methods are based on existing segmentation techniques previously implemented on image lattices. Using a watershed adjacency graph greatly reduces their memory footprint and computational cost. We demonstrate the practicality and versatility of this approach with several experiments on 2D and 3D datasets.