Semi Supervised Learning without label propagation
One strategy that seems good here is instance-level constrained clustering. These methods are semi-supervised algorithm that have "must-link" and "cannot-link" constraints between instances of known labels. So in your example, you would bind the 4 pairs (red, blue), (red, yellow), (blue, yellow), and (man, woman) as "must-link", and the 6 pairs (red, man), (red, woman), ..., (yellow, woman) as "cannot-link".

The results are similar to unsupervised clustering. For example, if you were to use DBSCAN (ignoring the labels/constraints), you would not need to specify the number of clusters/groups you're trying to achieve, and the algorithm would even find "outliers".

In fact, there is a version of DBSCAN that supports instance-level constraints, called C-DBSCAN. It is described in the work "Density-based semi-supervised clustering" by Ruiz et al (2010).

I do not know of any out-of-the-box implementations available, but I have a working version of C-DBSCAN I implemented for an experiment. However it is not documented nor is it performant/production level. You can find it at my lab's repository if you're interested (also contains the C-DenStream, which is the data streams version of it, but it does not seem to fit your problem).