login
Chromatic number (or Heawood number) of nonorientable surface with n crosscaps.
(Formerly M3265 N1318)
3

%I M3265 N1318 #31 Jun 30 2017 09:09:28

%S 4,6,7,7,8,9,9,10,10,10,11,11,12,12,12,13,13,13,13,14,14,14,15,15,15,

%T 15,16,16,16,16,16,17,17,17,17,18,18,18,18,18,19,19,19,19,19,19,20,20,

%U 20,20,20,21,21,21,21,21,21,22,22,22,22,22,22,22,23,23,23,23,23,23,24,24,24,24

%N Chromatic number (or Heawood number) of nonorientable surface with n crosscaps.

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

%D J. L. Gross and J. Yellen, eds., Handbook of Graph Theory, CRC Press, 2004; p. 368 and 631.

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

%H T. D. Noe, <a href="/A000703/b000703.txt">Table of n, a(n) for n = 0..1000</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 G. A. Dirac, <a href="http://dx.doi.org/10.4153/CJM-1952-043-9">Map-color theorems</a>, Canad. J. Math., 4 (1952), 480ff.

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

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

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

%p A000703:=n->floor((7+sqrt(1+24*n))/2): seq(A000703(n), n=0..150); # _Wesley Ivan Hurt_, Apr 24 2017

%t Floor[(7+Sqrt[1+24*Range[0,80]])/2] (* _Harvey P. Dale_, Feb 03 2012 *)

%o (Haskell)

%o a000703 = floor . (/ 2) . (+ 7) . sqrt . (+ 1) . (* 24) . fromInteger

%o -- _Reinhard Zumkeller_, Dec 04 2012

%Y Cf. A000934 (the orientable case).

%K nonn,nice,easy

%O 0,1

%A _N. J. A. Sloane_