This site is supported by donations to The OEIS Foundation.



(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A230628 Maximum number of colors needed to color a planar map of several empires, each empire consisting of n countries. 1


%S 4,12,18,24,30,36,42,48,54,60,66,72,78,84,90,96,102,108,114,120,126,

%T 132,138,144,150,156,162,168,174,180,186,192,198,204,210,216,222,228,

%U 234,240,246,252,258,264,270,276,282,288,294,300,306,312

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

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

%C 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.

%C 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

%D M. Gardner, Mathematical Games Column, Scientific American, Feb. 1980, page 14.

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

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

%H Brad Jackson and Gerhard Ringel, <a href="http://resolver.sub.uni-goettingen.de/purl?GDZPPN002201143">Solution of Heawood's empire problem in the plane</a>, J. Reine Angew. Math. 347 (1984), 146-153.

%H Brad Jackson and Gerhard Ringel, <a href="http://dx.doi.org/10.1016/0095-8956(85)90082-6">Heawood's empire problem</a>, Journal of Combinatorial Theory, Series B 38.2 (1985): 168-178.

%H N. J. A. Sloane, <a href="/A230628/a230628.pdf">Illustrations of a(2)=12 and a(3)=18</a> [Annotated copy of part of a figure from Ian Stewart's Scientific American article referenced above]

%H N. J. A. Sloane, <a href="/A230628/a230628.png">Another illustration for a(2)=12</a> [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]

%H <a href="/index/Rec#order_02">Index entries for linear recurrences with constant coefficients</a>, signature (2,-1).

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

%F G.f.: (-2*x)*(x^2-2*x-2)/(x-1)^2. - _Daniel Forgues_, Mar 04 2016

%F a(n) = 2*a(n-1) - a(n-2) for n > 3. - _Wesley Ivan Hurt_, Mar 07 2016

%e 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.

%p A230628:=n->6*n: 4, seq(A230628(n), n=2..100); # _Wesley Ivan Hurt_, Mar 07 2016

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

%o (PARI) a(n)=if(n>1,6*n,4) \\ _Charles R Greathouse IV_, Dec 11 2013

%K nonn,easy,nice

%O 1,1

%A _N. J. A. Sloane_, Oct 29 2013

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified October 20 07:17 EDT 2018. Contains 316378 sequences. (Running on oeis4.)