An induced subgraph is called homogeneous if it is either a clique or an independent set. Let hom(G) denote the size of the largest homogeneous subgraph of a graph G. The classic result in Ramsey theory asserts that hom(G)>=(1/2)log n for any graph G on n vertices, and it is best possible apart from the value of the multiplicative constant. We study properties of graphs on n vertices with hom(G)<=C*log n for some constant C. We show that every such graph contains an induced subgraph of order alpha*n in which beta*n^(1/2) vertices have different degrees, where alpha and beta depend only on C. This proves a conjecture of Erdos, Faudree and Sos. Joint work with Benny Sudakov.