Color psychology is the study of the effect of colors on human behavior. This area of study is interesting and challenging because there is no simple 'one-size-fits all' mapping between a color and the message that color can evoke in a particular person. Nevertheless, many of our daily decisions are influenced by the color palettes being presented to us. In this paper, we propose a novel computational algorithm to create color palettes that convey certain messages. It starts by constructing a weighted graph of color categories and messages that are based on semantic similarities between vector representation of the messages and delta-E color similarities between colors. The color selection process for a given message includes applying a Personalized PageRank algorithm on the graph, treating the message nodes as the personalizing factors. As a result, we have a distribution of probabilities over all the color nodes that have higher probabilities for the nodes neighboring to given messages. Finally, palettes are ranked on the basis of visual aesthetics, novelty, and the conflicting/reinforcing messages they evoke. We have applied this work to several interesting use cases where artists and fashion designers used the resulting color palettes to assist their creation process.