A characterization for a set of partial partitions to define an X-tree

Abstract

Trees whose vertices are partially labelled by elements of a finite set X provide a natural way to represent partitions of subsets of X. The condition under which a given collection of such partial partitions of X can be represented by a tree has previously been characterized in terms of a chordal graph structure on an underlying intersection graph. In this paper, we obtain a related graph-theoretic characterization for the uniqueness of a tree representation of a set of partial partitions of X.