Graph colouring with non contiguous countries.

Question

I have a map containing a number of countries. Each country is made up of a maximum of $2$ non-contiguous sections (e.g. Mainland US and Alaska). What is the maximum number of colours that will be required to colour the graph such that. 1. neighbouring countries use different colours, and 2. If a country is made up of $2$ non-contiguous sectionseach section must have the same colour.

It's easy to come up with an example that requires $5$ colours. But I don't know the limit.

Edit Hagen came up with one that required $9$.

Answer 1

As pointed out by bof in the comments, in the paper "Map-colour theorem" by P.J. Heawood, published in 1890 in the Quarterly Journal of Pure and Applied Mathematics, not only is an upper bound of $12$ proven (essentially in the same way as in the other answer) but a matching lower bound of $12$ is shown.

That is, Heawood drew a map of $12$ countries, each in two pieces, such that each country borders every other country. Here is that map:

The image is taken from the archived copy of that volume of the journal which I found on https://gdz.sub.uni-goettingen.de/id/PPN600494829_0024. The paper is on pages 332-338, but the accompanying figure is on the last page.

Answer 2

In the map below, each of the nine countries is neighbour with every other country. Consequently, at least

$$9$$

colours may be needed.

---

Consider a map with $v$ vertices, $e$ edges, $f$ regions and $c\ge \frac 12f$ countries. We may assume wlog that each vertex in the map is of degree $3$. Then $$ 2e=3v$$ Assume thee are $f_\nu $ regions with exactly $\nu $ incident edges/vertices (perhaps with multiplicities). Then $$ f=\sum f_\nu$$ and $$2e=\sum \nu f\nu.$$ From Euler, $$\tag112=6v+6f-6e=6f-2e=\sum (6-\nu)f_\nu. $$ Among all maps that require the maximal number $\chi$ of colours, consider one that minimizes the positive integer $3f-c$. Then removing a one region country (e.g., by uniting it with one of its neighbours) as well as separating the regions of a two-region country into two countries decreases $3f-c$. By minimality, a map modified this way id $(\chi-1)$-colourable, and form such a colouring we obtain a $\chi$-colouring of the original map where only the one- of two-region country that we modified uses the last colour. It follows that every country in a minimal map is neighbour to at least $\chi-1$ other countries.

We refine $(1)$. Let $c_\nu$ be the number of one-region countries with $\nu$ edges, and for $\nu\le\mu$ let $c_{\nu,\mu}$ be the number of two-region countries where the regions have $\nu$ and $\mu$ edges, respectively. Then with $f_\nu=c_\nu+\sum_{\mu<\nu}c_{\mu,\nu}+\sum_{\mu\ge \nu}c_{\nu,\mu}$, we find $$12=\sum_{\nu}(6-\nu)c_\nu+\sum_{\nu,\mu\atop \nu\le\mu}(12-\nu-\mu)c_{\nu,\mu}.$$ As some summand on the right must be positive, we conclude that there must exist either a one-region country with $\nu \le 5$ neighbours (which cannot be the case in our minimal map as we already know that each such country must have $\nu \ge \chi-1\ge 8$ neighbours) or a two-region country with $\nu+\mu \le 11$ neighbours. We infer that

$$9\le\chi\le 12. $$