We show that all graphs G which are distinguishable from any non-isomorphic graph by the classical color-refinement procedure are compact. In other words, the applicability range for Tinhofer’s linear programming approach to isomorphism testing is at least as large as for the combinatorial approach based on color refinement.
Exploring the relationship between color refinement and compactness further, we study related combinatorial and algebraic graph properties introduced by Tinhofer and Godsil. We show that the corresponding classes of graphs form a hierarchy and we prove that recognizing each of these graph classes is P-hard. In particular, this gives a first complexity lower bound for recognizing compact graphs.