Both examples and verbal explanations play an important role in learning new concepts and categories. At the same time, learning from verbal explanations is not accounted for in most category learning models, and is not studied in the traditional category learning paradigm. We propose a rational category communication model that formally describes the process of communicating a category structure using both verbal explanations and visual examples in a pedagogical setting. We build our model based on the assumption that verbal instructions are best suited for communication of crude constraints on a category structure, while exemplars complement it by providing means for finer adjustments. Our empirical study demonstrates that verbal communication is indeed more robust to changes in stimuli dimensionality, but that its efficiency is adversely affected when distinguishing between categories requires perceptual precision. Communicating through examples has a reversed pattern. We hope that both the proposed experimental paradigm and the computational model would facilitate further research into the relative roles of verbal and exemplar communication in category learning.