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

 

Logo

Invitation: celebrating 50 years of OEIS, 250000 sequences, and Sloane's 75th, there will be a conference at DIMACS, Rutgers, Oct 9-10 2014.

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A000934 Chromatic number (or Heawood number) Chi(n) of surface of genus n.
(Formerly M3292 N1327)
8
4, 7, 8, 9, 10, 11, 12, 12, 13, 13, 14, 15, 15, 16, 16, 16, 17, 17, 18, 18, 19, 19, 19, 20, 20, 20, 21, 21, 21, 22, 22, 22, 23, 23, 23, 24, 24, 24, 24, 25, 25, 25, 25, 26, 26, 26, 27, 27, 27, 27, 28, 28, 28, 28, 28, 29, 29, 29, 29, 30, 30, 30, 30, 31, 31, 31, 31, 31, 32, 32 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,1

COMMENTS

a(0) = 4 is the celebrated four-color theorem.

"In 1890 P. Heawood discovered the formula ... and proved that the number of colors required to color a map on an n-holed torus (n =>1) is at most Chi(n). In 1968 G. Ringel and J. W. T. Youngs succeeded in showing that for every n>=1, there is a configuration of Chi(n) countries on an n-holed torus such that each country shares a border with each of the Chi(n)-1 other countries; this shows that Chi(n) colors may be necessary. This completed the proof that Heawood's formula is indeed the correct chromatic number function for the n-holed torus." ... "Heawood's formula is in fact valid for n = 0." - Stan Wagon.

REFERENCES

K. Appel and W. Haken, Every planar map is four colorable. I. Discharging. Illinois J. Math. 21 (1977), 429-490.

K. Appel and W. Haken, Every planar map is four colorable. II. Reducibility. Illinois J. Math. 21 (1977), 491-567.

K. Appel and W. Haken, Every planar map is four colorable. With the collaboration of J. Koch. Contemporary Mathematics, 98. American Mathematical Society, Providence, RI, 1989. xvi+741 pp. ISBN: 0-8218-5103-9.

K. Appel and W. Haken, "The Four-Color Problem" in Mathematics Today (L. A. Steen editor), Springer NY 1978.

K. Appel and W. Haken, "The Four-Color proof suffices", Mathematical Intelligencer 8 no.1 pp. 10-20 1986.

K. Appel and W. Haken, "The Solution of the Four-Color Map Problem", Scientific American vol. 237 no.4 pp. 108-121 1977.

D. Barnett, Map coloring, Polyhedra and The Four-Color Problem, Dolciani Math. Expositions No. 8, Math. Asso. of Amer., Washington DC 1984.

J. H. Cadwell, Topics in Recreational Mathematics, Chapter 8 pp. 76-87 Cambridge Univ. Press 1966.

K. J. Devlin, All The Math That's Fit To Print, Chap. 17; 67 pp. 46-8; 161-2 MAA Washington DC 1994.

K. J. Devlin, Mathematics: The New Golden Age, Chapter 7, Columbia Univ. Press NY 1999.

M. Gardner, New Mathematical Diversions, Chapter 10 pp. 113-123, Math. Assoc. of Amer. Washington DC 1995.

J. L. Gross and T. W. Tucker, Topological Graph Theory, Wiley, 1987; see Table 5.1 p. 221.

M. E. Lines, Think of a Number, Chapter 10 pp. 91-100 Institute of Physics Pub. London 1990.

G. Ringel and J. W. T. Youngs, Solution of the Heawood map-coloring problem, Proc. Nat. Acad. Sci. USA, 60 (1968), 438-445.

Robertson, N.; Sanders, D.; Seymour, P. and Thomas, R., The four-color theorem. J. Combin. Theory Ser. B 70 (1997), no. 1, 2-44.

Robertson, N.; Sanders, D. P.; Seymour, P. and Thomas, R., A new proof of the four-color theorem. Electron. Res. Announc. Amer. Math. Soc. 2 (1996), no. 1, 17-25.

W. W. Rouse Ball & H. S. M. Coxeter, Mathematical Recreations and Essays, Chapter VIII pp. 222-242 Dover NY 1987.

W. L. Schaaf, Recreational Mathematics. A guide to the literature, Chapter 4.7 pp. 74-6 NCTM Washington DC 1963.

W. L. Schaaf, A Bibliography of Recreational Mathematics Vol. 2, Chapter 4.6 pp. 75-9 NCTM Washington DC 1972.

N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

I. Stewart, From Here to Infinity, Chapter 8 pp. 104-112, Oxford Univ.Press 1996.

H. Tietze, Famous Problems of Mathematics, Chapter XI pp. 226-242 Graylock Press Baltimore MD 1966.

Stan Wagon, Mathematica In Action, W.H. Freeman and Company, NY, 1991, pages 232 - 237.

R. Wilson, Four Colors Suffice, Princeton Univ. Press, 2002.

LINKS

T. D. Noe, Table of n, a(n) for n=0..1000

P. Alfeld, The Four Color Map Problem

K. Devlin, Last doubts removed about the proof of the Four Color Theorem

P. D\"orre, Every planar map is 4-color and 5-choosable

R. E. Kenyon, Jr., Toward an Inductive Solution for the Four Color Problem

C. Lozier, The Four Color Theorem

MegaMath, Four Color Theorem

J. J. O'Connor & E. F. Robertson, The four color theorem

G. Ringel & J. W. T. Youngs, Solution Of The Heawood Map-Coloring Problem

N. Robertson et al., The Four Color Theorem

D. S. Silver, Map Quest : Review of "Four Colors Suffice" by R.Wilson

Eric Weisstein's World of Mathematics, Chromatic Number

Eric Weisstein's World of Mathematics, Heawood Conjecture

Eric Weisstein's World of Mathematics, Torus Coloring

FORMULA

a(n) = floor( (7+sqrt(1+48n))/2 ).

MAPLE

A000934 := n-> floor((7+sqrt(1+48*n))/2);

MATHEMATICA

Table[ Floor[ N[(7 + Sqrt[48n + 1])/2] ], {n, 0, 100} ]

PROG

(Haskell)

a000934 = floor . (/ 2) . (+ 7) . sqrt . (+ 1) . (* 48) . fromInteger

-- Reinhard Zumkeller, Dec 03 2012

CROSSREFS

Cf. A000703, A006343.

Sequence in context: A179620 A082390 A011517 * A180692 A004710 A060257

Adjacent sequences:  A000931 A000932 A000933 * A000935 A000936 A000937

KEYWORD

easy,nice,nonn

AUTHOR

N. J. A. Sloane.

EXTENSIONS

More terms from Robert G. Wilson v, Dec 08 2000

STATUS

approved

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

Content is available under The OEIS End-User License Agreement .

Last modified August 20 10:35 EDT 2014. Contains 245797 sequences.