A230628 Maximum number of colors needed to color a planar map of several empires, each empire consisting of n countries.

4, 12, 18, 24, 30, 36, 42, 48, 54, 60, 66, 72, 78, 84, 90, 96, 102, 108, 114, 120, 126, 132, 138, 144, 150, 156, 162, 168, 174, 180, 186, 192, 198, 204, 210, 216, 222, 228, 234, 240, 246, 252, 258, 264, 270, 276, 282, 288, 294, 300, 306, 312

Offset

1,1

Comments

The countries in an empire must all have the same color; adjacent empires must have different colors.

The case n=1 is the four-color theorem: any planar map with any number of countries can be colored with 4 colors, so a(1)=4.

Obviously, replacing "each empire consisting of n countries" with "each empire consisting of at most n countries" yields the same sequence, since we are considering the worst case. - Daniel Forgues, Apr 03 2016

References

P. J. Heawood, "Map colour theorem," Quart. J. Math. Oxford Ser. 2., 24, 332-338 (1890).

Links

Table of n, a(n) for n=1..52.

Martin Gardner, The coloring of unusual maps leads into unchartered territory, Mathematical Games Column, Scientific American, Feb. 1980, page 14.

Brad Jackson and Gerhard Ringel, Solution of Heawood's empire problem in the plane, J. Reine Angew. Math. 347 (1984), 146-153.

Brad Jackson and Gerhard Ringel, Heawood's empire problem, Journal of Combinatorial Theory, Series B 38.2 (1985): 168-178.

N. J. A. Sloane, Illustrations of a(2)=12 and a(3)=18 [Annotated copy of part of a figure from Ian Stewart's Scientific American article referenced above]

N. J. A. Sloane, Another illustration for a(2)=12 [This symmetrical map was drawn by Scott Kim (see Gardner, 1980), the colors were assigned by Jackson and Ringel (1984), and the map was then colored by hand]

Ian Stewart, The rise and fall of the lunar m-pire, Mathematical Recreations Column, Scientific American, 268 (April 1993), 120-121.

Index entries for linear recurrences with constant coefficients, signature (2,-1).

Formula

a(1)=4; thereafter a(n) = 6*n (See Jackson & Ringel 1984).

G.f.: (-2*x)*(x^2-2*x-2)/(x-1)^2. - Daniel Forgues, Mar 04 2016

a(n) = 2*a(n-1) - a(n-2) for n > 3. - Wesley Ivan Hurt, Mar 07 2016

E.g.f.: 2*x*(3*exp(x) - 1). - Stefano Spezia, Jul 26 2022

Example

For n=2, we have a number of empires (12 in the top part of the illustration above), each empire having two countries. The illustration shows an example where all 12 colors are needed.

Maple

A230628:=n->6*n: 4, seq(A230628(n), n=2..100); # Wesley Ivan Hurt, Mar 07 2016

Mathematica

Join[{4, 12, 18}, LinearRecurrence[{2, -1}, {24, 30}, 50]] (* Harvey P. Dale, Dec 05 2014 *)

Prog

(PARI) a(n)=if(n>1, 6*n, 4) \\ Charles R Greathouse IV, Dec 11 2013

Crossrefs

Cf. A008588.

Sequence in context: A111371 A078514 A324519 * A074285 A301252 A057311

Adjacent sequences: A230625 A230626 A230627 * A230629 A230630 A230631

Keyword

nonn,easy,nice

Author

N. J. A. Sloane, Oct 29 2013

Status

approved