Domino question

[David Wilson]

In response to Richard Guy's criticisms, let me restate my problem by 
example.

Let there be a standard set of dominoes with n distinct numbers, 0 through 
n-1. Thus a standard set of 28 double-6 dominoes would represent the case n 
= 7.

The case n = 1 is the double-0 set consisting of the single 0-0 domino. This 
can be laid out on the grid as follows:

0 0

The 0's form a single 2-omino, so a(1) = 2.

The case n = 2 is the double-1 set consisting of the 3 dominoes 0-0, 0-1, 
and 1-1. These can be laid out on the grid as follows:

0 0 1
0 1 1

The 0's and 1's each form a 3-omino, so there are two polyominoes in this 
arrangement. Clearly we cannot form fewer, so a(2) = 2.

Similarly, for the case n = 3, the 6 double-2 dominoes can be arranged as:

  2 0 0 0
  2 2 0 1
  2 1 1 1

which form three polyominoes, again we cannot form fewer, so a(3) = 3.

For n = 4, we have 10 double-3 dominoes. We could arrange these on the grid 
in this way:

  2 2 2 1
  2 2 0 1
  3 0 0 1
  3 0 0 1
  3 3 3 1

so that the minimum of 4 polyominoes is formed, and a(4) = 4.

Though my examples all happen to be rectangular, this is not required.

For n = 5 (the double-4 polyominoes), we cannot form 5 polyominoes, as this 
would imply 5 pairwise adjacent regions in the plane, forbidden by the 
4-color theorem. Hence a(5) > 5, I suspect a(5) = 6.

Can we extend this?

Can we do better if we omit the doubles dominoes (0-0, 1-1, etc).
-----

Thinking about this led me to the following problem:

What is the smallest possible number of regions in a planar map that is 
colored in n colors, and for any pair of distinct colors, there exists an 
adjacent pair of regions having those colors?