2
$\begingroup$

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$.

$\endgroup$
4
  • $\begingroup$ The US is a non-example because of Hawaii. $\endgroup$
    – RobPratt
    May 1, 2020 at 17:09
  • $\begingroup$ It's easy to come up with an example for what? $8$ colours? Then you are done. I readily found a map for $7$ colours only (by merging two dodekahedra) $\endgroup$ May 1, 2020 at 17:50
  • 1
    $\begingroup$ In the light of my answer, "easy to see that it must be $\le 8$" seems not to be right. $\endgroup$ May 1, 2020 at 20:11
  • 1
    $\begingroup$ According to Graph Coloring Problems by Tommy R. Jensen and Bjarne Toft, this is "Heawood's empire problem" $H(\varepsilon,m)$ for Euler characteristic $\varepsilon=2$ and $2$-part "empires", and in this case the answer $H(2,2)=12$ was proved by P. J. Heawood, Map colour problem, Quart. J. Pure Appl. Math, 24 (1890), 332–338. Heawood proved the upper bound $$H(\varepsilon,m)\le\left\lfloor\frac12\cdot\left(6m+1+\sqrt{(6m+1)^2-24\varepsilon}\right)\right\rfloor$$ for all cases except $\varepsilon=2,m=1$. $\endgroup$
    – bof
    May 2, 2020 at 14:10

2 Answers 2

5
$\begingroup$

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

$$9$$

colours may be needed.

enter image description here


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. $$

$\endgroup$
1
  • $\begingroup$ Well that's quite unteresting, seems it requires more colours then I thought. $\endgroup$ May 2, 2020 at 9:47
4
$\begingroup$

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:

enter image description here

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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .