The segmentation of colour pictures in a graph-theoretical context is considered. The procedure aims at identifying, extracting and classifying visually important features on the image plane, such as regions of homogeneous colour and chromatic transitions. Well established principles of colour theory and graph theory are combined to obtain a unified representation of a colour picture. The picture is represented by means of a weighted graph, constructed so as to reflect the specification of the colour space employed as well as important relationships between picture elements. A spanning tree of the graph is obtained by iteratively minimising a specific picture distortion measure. This tree structure describes a hierarchy of partitions on the image plane. Each partition comprises disjoint regions containing elements with similar attribute. Due to the fact that region identification and edge detection form dual problems from the graph-theoretical viewpoint, region contours defined by such partitions form a hierarchy. To avoid artificial contouring, a specific type of artefact introduced by the segmentation algorithm, the use of higher level information, is considered. It is shown that, when texture (which is taken into account at an intermediate stage of picture segmentation) is combined with colour as joint similarity attributes of regions, an improved hierarchical description of contours is possible. This facilitates the progressive elimination of the undesirable contours and leads to the visual enhancement of the segmentation obtained.