login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
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. 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 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.
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
Seiichi Manyama, Table of n, a(n) for n = 0..10000 (terms 0..1000 from T. D. Noe)
K. Appel and W. Haken, Every planar map is four colorable. I. Discharging, Illinois J. Math. 21 (1977), no. 3, 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, The Four-Color proof suffices, Mathematical Intelligencer 8 no.1 pp. 10-20 1986.
P. Dörre, Every planar map is 4-color and 5-choosable, arXiv:math/0408384 [math.GM], 2004-2013.
MegaMath, Four Color Theorem [Dead link]
J. J. O'Connor & E. F. Robertson, The four color theorem
G. Ringel & J. W. T. Youngs, Solution Of The Heawood Map-Coloring Problem, Proc. Nat. Acad. Sci. USA, 60 (1968), 438-445.
N. Robertson et al., The Four Color Theorem
N. Robertson, D. Sanders, P. Seymour and R. Thomas, The four-color theorem, J. Combin. Theory Ser. B 70 (1997), no. 1, 2-44.
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
Sequence in context: A333202 A082390 A011517 * A180692 A004710 A060257
KEYWORD
easy,nice,nonn
AUTHOR
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 | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 19 01:57 EDT 2024. Contains 370952 sequences. (Running on oeis4.)