How to colorize a face of a Mesh

Hello everybody! So, I want to achieve something like this:

I'm able to do that. I do it by coloring the vertexes of my mesh. But i have to use this technique: http://answers.unity3d.com/questions/773982/color-triangle-on-mesh.html

Which is pretty bad from my perspective. Since I want to modify the colors at runtime. And I have to loop through all the verticies. The more verticies the slower it gets...

So I was wondering if there is another technique that I dont know. That maybe doesn't change the amount of verticies on the Model.

The example here is made in OpenGL and Java. But I hope i can achieve this in Unity aswell. (:

Thanks for the Answers already. Cheers.

Btw.. If there is something wrong with my question -> Tell me. Thank you (: