In this paper we consider the exogenous indifference classes model of Barberá and Ehlers (2011) and Sato (2009) and analyze further the relationship between the structure of indifference classes across agents and dictatorship results. The key to our approach is the pairwise partition graph. We provide necessary conditions on these graphs for strategy-proofness and unanimity (or efficiency) to imply dictatorship. These conditions are not sufficient; we also provide separate stronger conditions that are sufficient. A full characterization is obtained in the case of two agents for domains where strategy-proofness and efficiency imply dictatorship. © 2015, Springer-Verlag Berlin Heidelberg.