

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 fourcolor theorem.
"In 1890 P. Heawood discovered the formula ... and proved that the number of colors required to color a map on an nholed 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 nholed 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 nholed 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. With the collaboration of J. Koch. Contemporary Mathematics, 98. American Mathematical Society, Providence, RI, 1989. xvi+741 pp. ISBN: 0821851039.
K. Appel and W. Haken, "The FourColor Problem" in Mathematics Today (L. A. Steen editor), Springer NY 1978.
K. Appel and W. Haken, "The Solution of the FourColor Map Problem", Scientific American vol. 237 no.4 pp. 108121 1977.
D. Barnett, Map coloring, Polyhedra and The FourColor Problem, Dolciani Math. Expositions No. 8, Math. Asso. of Amer., Washington DC 1984.
J. H. Cadwell, Topics in Recreational Mathematics, Chapter 8 pp. 7687 Cambridge Univ. Press 1966.
K. J. Devlin, All The Math That's Fit To Print, Chap. 17; 67 pp. 468; 1612 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. 113123, 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. 91100 Institute of Physics Pub. London 1990.
Robertson, N.; Sanders, D. P.; Seymour, P. and Thomas, R., A new proof of the fourcolor theorem. Electron. Res. Announc. Amer. Math. Soc. 2 (1996), no. 1, 1725.
W. W. Rouse Ball & H. S. M. Coxeter, Mathematical Recreations and Essays, Chapter VIII pp. 222242 Dover NY 1987.
W. L. Schaaf, Recreational Mathematics. A guide to the literature, Chapter 4.7 pp. 746 NCTM Washington DC 1963.
W. L. Schaaf, A Bibliography of Recreational Mathematics Vol. 2, Chapter 4.6 pp. 759 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. 104112, Oxford Univ.Press 1996.
H. Tietze, Famous Problems of Mathematics, Chapter XI pp. 226242 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

Seiichi Manyama, Table of n, a(n) for n = 0..10000 (terms 0..1000 from T. D. Noe)
P. Alfeld, The Four Color Map Problem
K. Appel and W. Haken, Every planar map is four colorable. I. Discharging, Illinois J. Math. 21 (1977), no. 3, 429490.
K. Appel and W. Haken, Every planar map is four colorable. II. Reducibility. Illinois J. Math. 21 (1977), 491567.
K. Appel and W. Haken, The FourColor proof suffices, Mathematical Intelligencer 8 no.1 pp. 1020 1986.
K. Devlin, Last doubts removed about the proof of the Four Color Theorem
P. DÃ¶rre, Every planar map is 4color and 5choosable, arXiv:math/0408384 [math.GM], 20042013.
R. K. Guy, Letters to N. J. A. Sloane, JuneAugust 1968
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 MapColoring Problem, Proc. Nat. Acad. Sci. USA, 60 (1968), 438445.
N. Robertson et al., The Four Color Theorem
N. Robertson, D. Sanders, P. Seymour and R. Thomas, The fourcolor theorem, J. Combin. Theory Ser. B 70 (1997), no. 1, 244.
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
(MAGMA) [Floor((7+Sqrt(1+48*n))/2): n in [0..70]]; // Vincenzo Librandi, Jul 09 2017


CROSSREFS

Cf. A000703, A006343.
Sequence in context: A310936 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



