Free
Faster access than browser!

# Four color theorem

In mathematics, the four color theorem, or the four color map theorem, states that, given any separation of a plane into contiguous regions, producing a figure called a map, no more than four colors are required to color the regions of the map so that no two adjacent regions have the same color. [1]

92 relations: Alfred Kempe, Apollonian network, Augustus De Morgan, Azerbaijan, Big O notation, Cartography, Compactness theorem, Computational complexity theory, Computer-assisted proof, Connected space, Coq, Cuboid, Daniel P. Sanders, De Bruijn–Erdős theorem (graph theory), Discharging method (discrete mathematics), Discrete Mathematics (journal), Dorothea Blostein, Dror Bar-Natan, Enclave and exclave, Euler characteristic, Finite type invariant, First-order logic, Five color theorem, Floor and ceiling functions, Francis Guthrie, Genus (mathematics), Geographic contiguity, Georges Gonthier, Gerhard Ringel, German Mathematical Society, Glossary of graph theory terms, Graph (discrete mathematics), Graph coloring, Graph theory, Grötzsch's theorem, Hadwiger conjecture (graph theory), Hadwiger–Nelson problem, Heawood conjecture, Heinrich Heesch, Hugo Hadwiger, Immersion (mathematics), John William Theodore Youngs, Julius Petersen, Kaliningrad Oblast, Kempe chain, Kenneth Appel, Kenneth O. May, Klein bottle, Kurt Gödel, Lie algebra, ... Expand index (42 more) »

## Alfred Kempe

Sir Alfred Bray Kempe DCL FRS (6 July 1849, Kensington, London – 21 April 1922, London) was a mathematician best known for his work on linkages and the four colour theorem.

## Apollonian network

In combinatorial mathematics, an Apollonian network is an undirected graph formed by a process of recursively subdividing a triangle into three smaller triangles.

## Augustus De Morgan

Augustus De Morgan (27 June 1806 – 18 March 1871) was a British mathematician and logician.

No description.

## Big O notation

Big O notation is a mathematical notation that describes the limiting behaviour of a function when the argument tends towards a particular value or infinity.

## Cartography

Cartography (from Greek χάρτης chartēs, "papyrus, sheet of paper, map"; and γράφειν graphein, "write") is the study and practice of making maps.

## Compactness theorem

In mathematical logic, the compactness theorem states that a set of first-order sentences has a model if and only if every finite subset of it has a model.

## Computational complexity theory

Computational complexity theory is a branch of the theory of computation in theoretical computer science that focuses on classifying computational problems according to their inherent difficulty, and relating those classes to each other.

## Computer-assisted proof

A computer-assisted proof is a mathematical proof that has been at least partially generated by computer.

## Connected space

In topology and related branches of mathematics, a connected space is a topological space that cannot be represented as the union of two or more disjoint nonempty open subsets.

## Coq

In computer science, Coq is an interactive theorem prover.

## Cuboid

In geometry, a cuboid is a convex polyhedron bounded by six quadrilateral faces, whose polyhedral graph is the same as that of a cube.

## Daniel P. Sanders

Daniel P. Sanders is an American mathematician.

## De Bruijn–Erdős theorem (graph theory)

In graph theory, the De Bruijn–Erdős theorem states that, in graph coloring for an infinite graph, the number of colors needed is the same as the largest number of colors needed by any of its finite subgraphs (if this number is finite).

## Discharging method (discrete mathematics)

The discharging method is a technique used to prove lemmas in structural graph theory.

## Discrete Mathematics (journal)

Discrete Mathematics is a biweekly peer-reviewed scientific journal in the broad area of discrete mathematics, combinatorics, graph theory, and their applications.

## Dorothea Blostein

Dorothea Haken Blostein is a Canadian computer scientist who works as a professor of computer science at Queen's University.

## Dror Bar-Natan

Dror Bar-Natan (דרוֹר בָר-נָתָן; born January 30, 1966) is a Professor at the University of Toronto Department of Mathematics, Canada.

## Enclave and exclave

An enclave is a territory, or a part of a territory, that is entirely surrounded by the territory of one other state.

## Euler characteristic

In mathematics, and more specifically in algebraic topology and polyhedral combinatorics, the Euler characteristic (or Euler number, or Euler&ndash;Poincaré characteristic) is a topological invariant, a number that describes a topological space's shape or structure regardless of the way it is bent.

## Finite type invariant

In the mathematical theory of knots, a finite type invariant, or Vassiliev invariant, is a knot invariant that can be extended (in a precise manner to be described) to an invariant of certain singular knots that vanishes on singular knots with m + 1 singularities and does not vanish on some singular knot with 'm' singularities.

## First-order logic

First-order logic—also known as first-order predicate calculus and predicate logic—is a collection of formal systems used in mathematics, philosophy, linguistics, and computer science.

## Five color theorem

The five color theorem is a result from graph theory that given a plane separated into regions, such as a political map of the counties of a state, the regions may be colored using no more than five colors in such a way that no two adjacent regions receive the same color.

## Floor and ceiling functions

In mathematics and computer science, the floor function is the function that takes as input a real number x and gives as output the greatest integer less than or equal to x, denoted \operatorname(x).

## Francis Guthrie

Francis Guthrie (born 22 January 1831 in London; d. 19 October 1899 in Claremont, Cape Town) was a South African mathematician and botanist who first posed the Four Colour Problem in 1852.

## Genus (mathematics)

In mathematics, genus (plural genera) has a few different, but closely related, meanings.

## Geographic contiguity

Geographic contiguity is the characteristic in geography of political or geographical land divisions, as a group, not being interrupted by other land or water.

## Georges Gonthier

Georges Gonthier is one of the leading practitioners in formal mathematics.

## Gerhard Ringel

Gerhard Ringel (October 28, 1919 in Kollnbrunn, Austria – June 24, 2008 in Santa Cruz, California) was a German mathematician who earned his Ph.D. from the University of Bonn in 1951.

## German Mathematical Society

The German Mathematical Society (Deutsche Mathematiker-Vereinigung &ndash; DMV) is the main professional society of German mathematicians.

## Glossary of graph theory terms

This is a glossary of graph theory terms.

## Graph (discrete mathematics)

In mathematics, and more specifically in graph theory, a graph is a structure amounting to a set of objects in which some pairs of the objects are in some sense "related".

## Graph coloring

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 graph subject to certain constraints.

## Graph theory

In mathematics, graph theory is the study of graphs, which are mathematical structures used to model pairwise relations between objects.

## Grötzsch's theorem

In the mathematical field of graph theory, Grötzsch's theorem is the statement that every triangle-free planar graph can be colored with only three colors.

In graph theory, the Hadwiger conjecture (or Hadwiger's conjecture) states that, if all proper colorings of an undirected graph G use k or more colors, then one can find k disjoint connected subgraphs of G such that each subgraph is connected by an edge to each other subgraph.

In geometric graph theory, the Hadwiger–Nelson problem, named after Hugo Hadwiger and Edward Nelson, asks for the minimum number of colors required to color the plane such that no two points at distance 1 from each other have the same color.

## Heawood conjecture

In graph theory, the Heawood conjecture or Ringel–Youngs theorem gives a lower bound for the number of colors that are necessary for graph coloring on a surface of a given genus.

## Heinrich Heesch

Heinrich Heesch (June 25, 1906 &ndash; July 26, 1995) was a German mathematician.

Hugo Hadwiger (23 December 1908 in Karlsruhe, Germany &ndash; 29 October 1981 in Bern, Switzerland) was a Swiss mathematician, known for his work in geometry, combinatorics, and cryptography.

## Immersion (mathematics)

In mathematics, an immersion is a differentiable function between differentiable manifolds whose derivative is everywhere injective.

## John William Theodore Youngs

John William Theodore Youngs (usually cited as J. W. T. Youngs, known as Ted Youngs; 21 August 1910 Bilaspur, Chhattisgarh, India – 20 July 1970 Santa Cruz, California) was an American mathematician.

## Julius Petersen

Julius Peter Christian Petersen (16 June 1839, Sorø, West Zealand &ndash; 5 August 1910, Copenhagen) was a Danish mathematician.

Kaliningrad Oblast (Калинингра́дская о́бласть, Kaliningradskaya oblast), often referred to as the Kaliningrad Region in English, or simply Kaliningrad, is a federal subject of the Russian Federation that is located on the coast of the Baltic Sea.

## Kempe chain

In mathematics, a Kempe chain is a device used mainly in the study of the four colour theorem.

## Kenneth Appel

Kenneth Ira Appel (October 8, 1932 – April 19, 2013) was an American mathematician who in 1976, with colleague Wolfgang Haken at the University of Illinois at Urbana-Champaign, solved one of the most famous problems in mathematics, the four-color theorem.

## Kenneth O. May

Kenneth O. May (July 8, 1915, in Portland, Oregon – December 1977, in Toronto) was an American mathematician and historian of mathematics, who developed May's theorem.

## Klein bottle

In topology, a branch of mathematics, the Klein bottle is an example of a non-orientable surface; it is a two-dimensional manifold against which a system for determining a normal vector cannot be consistently defined.

## Kurt Gödel

Kurt Friedrich Gödel (April 28, 1906 – January 14, 1978) was an Austrian, and later American, logician, mathematician, and philosopher.

## Lie algebra

In mathematics, a Lie algebra (pronounced "Lee") is a vector space \mathfrak g together with a non-associative, alternating bilinear map \mathfrak g \times \mathfrak g \rightarrow \mathfrak g; (x, y) \mapsto, called the Lie bracket, satisfying the Jacobi identity.

## Lower Peninsula of Michigan

The Lower Peninsula of Michigan is the southern of the two major landmasses of the U.S. state of Michigan, the other being the Upper Peninsula.

## MacTutor History of Mathematics archive

The MacTutor History of Mathematics archive is a website maintained by John J. O'Connor and Edmund F. Robertson and hosted by the University of St Andrews in Scotland.

## Map coloring

Map coloring is the act of assigning different colors to different features on a map.

## Masterpiece

Masterpiece, magnum opus (Latin, great work) or chef-d’œuvre (French, master of work, plural chefs-d’œuvre) in modern use is a creation that has been given much critical praise, especially one that is considered the greatest work of a person's career or to a work of outstanding creativity, skill, profundity, or workmanship.

## Mathematics

Mathematics (from Greek μάθημα máthēma, "knowledge, study, learning") is the study of such topics as quantity, structure, space, and change.

## MathOverflow

MathOverflow is a mathematics website, which serves both as a collaborative blog and an online community of mathematicians.

## Möbius strip

The Möbius strip or Möbius band, also spelled Mobius or Moebius, is a surface with only one side (when embedded in three-dimensional Euclidean space) and only one boundary.

## Microform

Microforms are scaled-down reproductions of documents, typically either films or paper, made for the purposes of transmission, storage, reading, and printing.

## Nakhchivan Autonomous Republic

The Nakhchivan Autonomous Republic (Naxçıvan Muxtar Respublikası) is a landlocked exclave of the Republic of Azerbaijan.

## Neil Robertson (mathematician)

George Neil Robertson (born November 30, 1938) is a mathematician working mainly in topological graph theory, currently a distinguished professor emeritus at the Ohio State University.

## Non-surveyable proof

In the philosophy of mathematics, a non-surveyable proof is a mathematical proof that is considered infeasible for a human mathematician to verify and so of controversial validity.

## Notices of the American Mathematical Society

Notices of the American Mathematical Society is the membership journal of the American Mathematical Society (AMS), published monthly except for the combined June/July issue.

## NP-completeness

In computational complexity theory, an NP-complete decision problem is one belonging to both the NP and the NP-hard complexity classes.

## Orientability

In mathematics, orientability is a property of surfaces in Euclidean space that measures whether it is possible to make a consistent choice of surface normal vector at every point.

## Paul Seymour (mathematician)

Paul Seymour (born July 26, 1950) is currently a professor at Princeton University; half in the department of mathematics and half in the program in applied and computational math.

## Percy John Heawood

Percy John Heawood (8 September 1861 Newport, Shropshire, England – 24 January 1955 Durham, England) was a British mathematician educated at Queen Elizabeth's School, Ipswich, and Exeter College, Oxford.

## Peter Tait (physicist)

Peter Guthrie Tait FRSE (28 April 1831 – 4 July 1901) was a Scottish mathematical physicist and early pioneer in thermodynamics.

## Philip Franklin

Philip Franklin (October 5, 1898 &ndash; January 27, 1965) was an American mathematician and professor whose work was primarily focused in analysis.

## Planar graph

In graph theory, a planar graph is a graph that can be embedded in the plane, i.e., it can be drawn on the plane in such a way that its edges intersect only at their endpoints.

## Proof assistant

In computer science and mathematical logic, a proof assistant or interactive theorem prover is a software tool to assist with the development of formal proofs by human-machine collaboration.

## Quartic function

In algebra, a quartic function is a function of the form where a is nonzero, which is defined by a polynomial of degree four, called a quartic polynomial.

## Robin Thomas (mathematician)

Robin Thomas is a mathematician working in graph theory at the Georgia Institute of Technology.

## RWTH Aachen University

RWTH Aachen University or Rheinisch-Westfälische Technische Hochschule AachenRWTH is the abbreviation of Rheinisch-Westfälische Technische Hochschule, which translates into "Rheinish-Westphalian Technical University".

## Snark (graph theory)

In the mathematical field of graph theory, a snark is a simple, connected, bridgeless cubic graph with chromatic index equal to 4.

## Szilassi polyhedron

The Szilassi polyhedron is a nonconvex polyhedron, topologically a torus, with seven hexagonal faces.

## The Athenaeum (British magazine)

The Athenaeum was a literary magazine published in London, England from 1828 to 1921.

## The Mathematical Intelligencer

The Mathematical Intelligencer is a mathematical journal published by Springer Verlag that aims at a conversational and scholarly tone, rather than the technical and specialist tone more common among academic journals.

## The New York Times

The New York Times (sometimes abbreviated as The NYT or The Times) is an American newspaper based in New York City with worldwide influence and readership.

## Theorem

In mathematics, a theorem is a statement that has been proven on the basis of previously established statements, such as other theorems, and generally accepted statements, such as axioms.

## Time complexity

In computer science, the time complexity is the computational complexity that describes the amount of time it takes to run an algorithm.

## Toroidal polyhedron

In geometry, a toroidal polyhedron is a polyhedron which is also a toroid (a g-holed torus), having a topological genus of 1 or greater.

## Torus

In geometry, a torus (plural tori) is a surface of revolution generated by revolving a circle in three-dimensional space about an axis coplanar with the circle.

## Transitive relation

In mathematics, a binary relation over a set is transitive if whenever an element is related to an element and is related to an element then is also related to.

## Triangle-free graph

In the mathematical area of graph theory, a triangle-free graph is an undirected graph in which no three vertices form a triangle of edges.

## Triangulation (geometry)

In geometry, a triangulation is a subdivision of a planar object into triangles, and by extension the subdivision of a higher-dimension geometric object into simplices.

## University College London

University College London (UCL) is a public research university in London, England, and a constituent college of the federal University of London.

## University of Illinois at Urbana–Champaign

The University of Illinois Urbana–Champaign (also known as U of I, Illinois, or colloquially as the University of Illinois or UIUC) is a public research university in the U.S. state of Illinois and the flagship institution of the University of Illinois System.

## Upper Peninsula of Michigan

The Upper Peninsula (UP), also known as Upper Michigan, is the northern of the two major peninsulas that make up the U.S. state of Michigan.

## Vertex (graph theory)

In mathematics, and more specifically in graph theory, a vertex (plural vertices) or node is the fundamental unit of which graphs are formed: an undirected graph consists of a set of vertices and a set of edges (unordered pairs of vertices), while a directed graph consists of a set of vertices and a set of arcs (ordered pairs of vertices).

## W. W. Rouse Ball

Walter William Rouse Ball, known as W. W. Rouse Ball (14 August 1850 – 4 April 1925), was a British mathematician, lawyer, and fellow at Trinity College, Cambridge from 1878 to 1905.

## Wolfgang Haken

Wolfgang Haken (born June 21, 1928 in Berlin, Germany) is a mathematician who specializes in topology, in particular 3-manifolds.

## 1-planar graph

In topological graph theory, a 1-planar graph is a graph that can be drawn in the Euclidean plane in such a way that each edge has at most one crossing point, where it crosses a single additional edge.

## References

Hey! We are on Facebook now! »