login
Chromatic number (or Heawood number) Chi(n) of surface of genus n.
(Formerly M3292 N1327)
8

%I M3292 N1327 #58 May 01 2023 10:03:21

%S 4,7,8,9,10,11,12,12,13,13,14,15,15,16,16,16,17,17,18,18,19,19,19,20,

%T 20,20,21,21,21,22,22,22,23,23,23,24,24,24,24,25,25,25,25,26,26,26,27,

%U 27,27,27,28,28,28,28,28,29,29,29,29,30,30,30,30,31,31,31,31,31,32,32

%N Chromatic number (or Heawood number) Chi(n) of surface of genus n.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

%H Seiichi Manyama, <a href="/A000934/b000934.txt">Table of n, a(n) for n = 0..10000</a> (terms 0..1000 from T. D. Noe)

%H P. Alfeld, <a href="http://www.math.utah.edu/~alfeld/math/4color.html">The Four Color Map Problem</a>

%H K. Appel and W. Haken, <a href="http://projecteuclid.org/euclid.ijm/1256049011">Every planar map is four colorable. I. Discharging</a>, Illinois J. Math. 21 (1977), no. 3, 429-490.

%H K. Appel and W. Haken, <a href="http://projecteuclid.org/euclid.ijm/1256049012">Every planar map is four colorable. II. Reducibility</a>. Illinois J. Math. 21 (1977), 491-567.

%H K. Appel and W. Haken, <a href="https://doi.org/10.1007/BF03023914">The Four-Color proof suffices</a>, Mathematical Intelligencer 8 no.1 pp. 10-20 1986.

%H K. Devlin, <a href="http://www.maa.org/devlin/devlin_01_05.html">Last doubts removed about the proof of the Four Color Theorem</a>

%H P. Dörre, <a href="http://arXiv.org/abs/math.CO/0408384">Every planar map is 4-color and 5-choosable</a>, arXiv:math/0408384 [math.GM], 2004-2013.

%H R. K. Guy, <a href="/A002186/a002186.pdf">Letters to N. J. A. Sloane, June-August 1968</a>

%H R. E. Kenyon, Jr., <a href="http://www.xenodochy.org/article/fourcolor.html">Toward an Inductive Solution for the Four Color Problem</a>

%H C. Lozier, <a href="http://bhs.broo.k12.wv.us/discrete/4Color.htm">The Four Color Theorem</a>

%H MegaMath, <a href="http://www.c3lanl.gov/maga-math/gloss/math/4ct.html">Four Color Theorem</a> [Dead link]

%H J. J. O'Connor & E. F. Robertson, <a href="http://www-gap.dcs.st-and.ac.uk/~history/HistTopics/The_four_colour_theorem.html">The four color theorem</a>

%H G. Ringel & J. W. T. Youngs, <a href="http://www.pnas.org/cgi/reprint/60/2/438.pdf">Solution Of The Heawood Map-Coloring Problem</a>, Proc. Nat. Acad. Sci. USA, 60 (1968), 438-445.

%H N. Robertson et al., <a href="http://www.math.gatech.edu/~thomas/FC/fourcolor.html">The Four Color Theorem</a>

%H N. Robertson, D. Sanders, P. Seymour and R. Thomas, <a href="https://doi.org/10.1006/jctb.1997.1750">The four-color theorem</a>, J. Combin. Theory Ser. B 70 (1997), no. 1, 2-44.

%H D. S. Silver, <a href="http://www.americanscientist.org/template/BookReviewTypeDetail/assetid/21979?&amp;print=yes">Map Quest : Review of "Four Colors Suffice" by R.Wilson</a>

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/ChromaticNumber.html">Chromatic Number</a>

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/HeawoodConjecture.html">Heawood Conjecture</a>

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/TorusColoring.html">Torus Coloring</a>

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

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

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

%o (Haskell)

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

%o -- _Reinhard Zumkeller_, Dec 03 2012

%o (Magma) [Floor((7+Sqrt(1+48*n))/2): n in [0..70]]; // _Vincenzo Librandi_, Jul 09 2017

%Y Cf. A000703, A006343.

%K easy,nice,nonn

%O 0,1

%A _N. J. A. Sloane_

%E More terms from _Robert G. Wilson v_, Dec 08 2000