The Heawood conjecture in graph theory gives an upper bound for the number of colors which are sufficient for graph coloring on a surface of a given genus. In Mathematics and Computer science, graph theory is the study of graphs: mathematical structures used to model pairwise relations between objects In Mathematics, especially in Order theory, an upper bound of a Subset S of some Partially ordered set ( P, &le In Graph theory, graph coloring is a special case of Graph labeling; it is an assignment of labels traditionally called "colors" to elements of a In Mathematics, specifically in Topology, a surface is a Two-dimensional Manifold. In Mathematics, genus has a few different but closely related meanings Topology Orientable surface It was proven in 1968 by Gerhard Ringel and J. Gerhard Ringel (born October 28, 1919, Kolnbrunn Austria Died June 24 2008 Santa Cruz California is a German Mathematician who earned his Ph W. T. Youngs. One case, the non-orientable Klein bottle, proved an exception to the general formula. A surface S in the Euclidean space R 3 is orientable if a two-dimensional figure (for example) cannot be moved around the surface and back In Mathematics, the Klein bottle is a certain non- orientable Surface, i An entirely different approach was needed for finding the number of colors needed for the sphere, eventually solved as the four color theorem. "Globose" redirects here See also Globose nucleus. A sphere (from Greek σφαίρα - sphaira, "globe The four color theorem (also known as the four color map theorem) states that given any plane separated into regions such as a political map of the states of a country

Formal statement

P.J. Heawood conjectured in 1890 that for a given genus g > 0, the minimum number of colors necessary to color all graphs drawn on an orientable surface of that genus (or equivalently to color the regions of any partition of the surface into simply connected regions) is given by

where is the floor function. Percy John Heawood ( 8 September, 1861 Newport Shropshire, England - 24 January, 1955 Durham, England In Mathematics, a conjecture is a Mathematical statement which appears resourceful but has not been formally proven to be true under the rules of In Mathematics and Computer science, the floor and ceiling functions map Real numbers to nearby Integers The

Replacing the genus by the Euler characteristic, we obtain a formula that covers both the orientable and non-orientable cases,

This relation holds, as Ringel and Youngs showed, for all surfaces except for the Klein bottle. In Mathematics, and more specifically in Algebraic topology and Polyhedral combinatorics, the Euler characteristic is a Topological invariant In Mathematics, the Klein bottle is a certain non- orientable Surface, i Franklin (1930) proved that the Klein bottle requires at most 6 colors, rather than 7 as predicted by the formula (see Franklin graph).

In one direction, the proof is straightforward: by manipulating the Euler characteristic, one can show that any graph embedded in the surface must have at least one vertex of degree less than the given bound. If one removes this vertex, and colors the rest of the graph, the small number of edges incident to the removed vertex ensures that it can be added back to the graph and colored without increasing the needed number of colors beyond the bound. In the other direction, the proof is more difficult, and involves showing that in each case (except the Klein bottle) a complete graph with a number of vertices equal to the given number of colors can be embedded on the surface. In the mathematical field of Graph theory, a complete graph is a Simple graph in which every pair of distinct vertices is connected by an

Example

A partition of the torus into seven mutually adjacent regions, requiring seven colors.

The torus has g = 1, so χ = 0. In Geometry, a torus (pl tori) is a Surface of revolution generated by revolving a Circle in three dimensional space about an axis Coplanar Therefore, as the formula states, any subdivision of the torus into regions can be colored using at most seven colors. The illustration shows a subdivision of the torus in which each of seven regions are adjacent to each other region; this subdivision shows that the bound of seven on the number of colors is tight for this case. The boundary of this subdivision forms an embedding of the Heawood graph onto the torus. In the mathematical field of Graph theory, the Heawood graph is an Undirected graph with 14 vertices and 21 edges

References

• Franklin, P. (1934). "A six color problem". J. Math. Phys. 13: 363–379.  

• Heawood, P. J. (1890). "Map colour theorem". Quart. J. Math. 24: 332–338.  

• Ringel, G. ; Youngs, J. W. T. (1968). "Solution of the Heawood map-coloring problem". Proc. Nat. Acad. Sci. USA 60: 438–445. doi:10.1073/pnas.60.2.438. A digital object identifier ( DOI) is a permanent identifier given to an Electronic document. MR0228378. Mathematical Reviews is a journal and online database published by the American Mathematical Society that contains brief synopses (and occasionally evaluations of many  

External links

• Eric W. Weisstein, Heawood Conjecture at MathWorld. Eric W Weisstein (born March 18, 1969, in Bloomington Indiana) is an Encyclopedist who created and maintains MathWorld MathWorld is an online Mathematics reference work created and largely written by Eric W