Both examples and verbal explanations play an important rolein learning new concepts and categories. At the same time,learning from verbal explanations is not accounted for in mostcategory learning models, and is not studied in the traditionalcategory learning paradigm. We propose a rational categorycommunication model that formally describes the process ofcommunicating a category structure using both verbal expla-nations and visual examples in a pedagogical setting. We buildour model based on the assumption that verbal instructions arebest suited for communication of crude constraints on a cat-egory structure, while exemplars complement it by providingmeans for finer adjustments. Our empirical study demonstratesthat verbal communication is indeed more robust to changesin stimuli dimensionality, but that its efficiency is adverselyaffected when distinguishing between categories requires per-ceptual precision. Communicating through examples has a re-versed pattern. We hope that both the proposed experimentalparadigm and the computational model would facilitate furtherresearch into the relative roles of verbal and exemplar commu-nication in category learning.