You can search for themes with certain colors using HEX value of color as search keyword. For e.g: Search for HEX:94090D will get you all themes using 94090D color.
However, search with color as starting point is not possible.
Thank you, I assume this means that the color I use to search must exactly match what is in the theme and I can't search for a theme containing a similar color. Right?
Yes. Search is for exact match.