The vascular structure of the retina consists of two kinds of vessels: arteries and veins. Together these vessels form the vascular graph. In this paper we present an approach to separating arteries and veins based on a pre-segmentation and a few hand-labelled vessel segments. We use a rule-based method to propagate the vessel labels through the vascular graph. We embed this task as double-layered constrained search problem steered by a heuristical AC-3 algorithm to overcome the NPhard computational complexity. Results are presented on vascular graphs generated from hand-made as well as on automatical segmentation.