

A230628


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


1



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
(list;
graph;
refs;
listen;
history;
text;
internal format)



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 fourcolor 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

M. Gardner, Mathematical Games Column, Scientific American, Feb. 1980, page 14.
P. J. Heawood, "Map colour theorem," Quart. J. Math. Oxford Ser. 2., 24, 332338 (1890).
Ian Stewart, The rise and fall of the lunar mpire, Mathematical Recreations Column, Scientific American, 268 (April 1993), 120121.


LINKS

Table of n, a(n) for n=1..52.
Brad Jackson and Gerhard Ringel, Solution of Heawood's empire problem in the plane, J. Reine Angew. Math. 347 (1984), 146153.
Brad Jackson and Gerhard Ringel, Heawood's empire problem, Journal of Combinatorial Theory, Series B 38.2 (1985): 168178.
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]
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^22*x2)/(x1)^2.  Daniel Forgues, Mar 04 2016
a(n) = 2*a(n1)  a(n2) for n > 3.  Wesley Ivan Hurt, Mar 07 2016


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

Sequence in context: A175704 A111371 A078514 * A074285 A057311 A063679
Adjacent sequences: A230625 A230626 A230627 * A230629 A230630 A230631


KEYWORD

nonn,easy,nice


AUTHOR

N. J. A. Sloane, Oct 29 2013


STATUS

approved



