The significant impact of coronary artery disease on cardiovascular health underscores the need for precise diagnostic methods. The SYNTAX score, based on the locations of stenoses in the coronary tree, provides a quantitative estimation of the disease’s complexity, allowing to settle on a treatment strategy. However, expert experience is required for visual localization of stenoses, which would be facilitated by automated labelling of the coronary segments. In this work we represent the connected structure of the coronary tree as a graph, extracted from the angiography image, onto which we apply a graph convolutional network to label the coronary segments according to the SYNTAX score scheme, before creating a multi-class segmentation mask. The method was trained and evaluated using the ARCADE dataset. The segment classification of graph nodes reached an F1-score of 53.68. Our approach achieved a mean F1-score of 45.43 for multiclass segmentation of the image after applying the entire pipeline. Although a baseline nnU-Net model achieves better performance (mean F1-score of 62.53), the results are comparable to other existing approaches and show that graph-based approaches are suitable for the complex task of coronary segment labelling.