In 2017 Day et al. introduced the notion of locality as a structural complexity-measure for patterns in the field of pattern matching established by Angluin in 1980. In 2019 Casel et al. showed that determining the locality of an arbitrary pattern is NP-complete. Inspired by hierarchical clustering, we extend the notion to coloured graphs, i.e., given a coloured graph determine an enumeration of the colours such that colouring the graph stepwise according to the enumeration leads to as few clusters as possible. Besides initial theoretical results on graph classes, we propose a priority search algorithm to compute the k-locality of a graph. This algorithm guarantees a correct result, while being faster by orders of magnitude than an exhaustive search over all permutations of colour enumerations. Finally, we perform a case study on a DBLP subgraph to demonstrate the potential of k-locality for knowledge discovery.