We present an approach for object class learning using a part-based shape categorization in RGB-augmented 3D point clouds captured from cluttered indoor scenes with a Kinect-like sensor. A graph representation is used to detect and categorize object instances based on part-constellations found in scenes. No assumptions like objects being placed on planar surfaces or constraints on their poses are required. Our approach consists of the following steps: 1) a Mean-Shift-based over-segmentation of a point cloud into atomic patches; 2) use of topological and geometric features to merge surface-homogeneous atomic patches into super patches; 3) an unsupervised classification of these parts that allows to symbolically label distinctively unknown object parts by their surface-structural appearance; and finally, 4) a graph generation procedure that reflects the constellation of the detected parts from object instances of certain shape categories. Furthermore, an inference procedure is presented that processes extracted part constellations of a scene to detect and categorize object instances. Experiments with challenging, cluttered scenes show that the segmentation procedure provides salient parts of objects which lead to a good categorization performance using the graph-based constellation model concept.