Artery/vein classification in fundus images is a prerequisite for the assessment of diseases such as diabetes, hypertension or other cardiovascular pathologies. One clinical measure used to assess the severity of cardiovascular risk is the retinal arterio-venous ratio (AVR), which significantly depends on the accuracy of vessel classification into arteries or veins. This paper proposes a novel method for artery/vein classification combining deep learning and graph propagation strategies. First, a convolutional neural network (CNN) is trained for the task of labeling vessel pixels into arteries or veins. A graph is then constructed from the retinal vascular network. The nodes are defined as the vessel branches and each edge gets associated to a cost evaluating if the two branches should have the same label. The CNN’s artery/vein classification is efficiently propagated through the minimum spanning tree of the graph. We validated our method on two publicly available databases. Our method achieves an accuracy of 93.3% on the DRIVE