I did a challenge map of Japan once showing the provinces of southwestern Honshu, the island of Shikoku and part of Kyushu, as participants in the Genpei War. As a way to politically define each province, as well as show which of the two sides in the conflict they supported, I included kammon (samurai house crests) as the political identifiers. So though you could use interior fills of each province with a different color, as you have above, you could create colored borders that work like the color fill to indicate the politics of a given province. Or, you could put in heraldic symbols, as in my example using kammon to differentiate each.

Here's a link to my Genpei War Map.