login
This site is supported by donations to The OEIS Foundation.

 

Logo

Annual appeal: Please make a donation to keep the OEIS running! Over 6000 articles have referenced us, often saying "we discovered this result with the help of the OEIS".
Other ways to donate

Hints
(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
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 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

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

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

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

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), 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]

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

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

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 December 12 20:04 EST 2017. Contains 295954 sequences.