'a fogkeféd piros' should also be accepted
Yes. And "a te fogkeféd piros" is also good.
Can't you say: piros a fogkeféd