Player A is allowed to draw a map with 'n' regions, and colour them in using 5 colours. Two connected regions cannot be of the same colour. This map is then given to Player B, who's job is to recolour the map using only 4 colours (she gets to choose which of the 5 original colours to try to eliminate). Player B's goal is to need to recolour as few regions as possible. Player A is trying to create a map which maximises the number of regions which require recolouring.
For instance, with n=10, I think this is the best Player A can do:
In this map, the yellow and blue regions are isomorphic. Suppose Player B recolours the yellow regions. Both yellow regions are in contact with regions of each of the other four colours. It requires four regions to be recoloured, for instance:
You will find similarly that choosing any other colour to eliminate means 4 regions will need to be recoloured.
Question: what is the relationship between 'n', the number of regions on the map, and C, the number of recolourings required (assuming both Players A and B are playing optimally)? Is it the case that C = approx 2n/5 ?