Translation:I want a bag in a different color.
It's still a verb here. A more literal translation of 違う色 would be "a color that differs". Relative clauses are simply placed before the noun they modify. Technically, this is also how adjectives work. 高いカバン technically uses a relative clause, i.e., "a bag that is expensive"
You add の to a verb to make it a noun. To use a verb as an adjective like in this sentence, you don't add anything, just use the plain form of the verb.
Verbs clauses can also be used just like adjectives to modify nouns. The following examples show us how this will allow us to make quite detailed and complicated sentences. The verb clause is highlighted.
（１） 先週に映画を見た人は誰？ - Who is person who watched movie last week?
（２） ボブは、いつも勉強する人だ。 - Bob is a person who always studies.
（３） 赤いズボンを買う友達はボブだ。 - Friend who buy red pants is Bob.
（４） 晩ご飯を食べなかった人は、映画で見た銀行に行った。 - Person who did not eat dinner went to the bank she saw at movie.