Logo
Unionpedia
Communication
Get it on Google Play
New! Download Unionpedia on your Android™ device!
Install
Faster access than browser!
 

Four color theorem

Index 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, ..., Lower Peninsula of Michigan, MacTutor History of Mathematics archive, Map coloring, Masterpiece, Mathematics, MathOverflow, Möbius strip, Microform, Nakhchivan Autonomous Republic, Neil Robertson (mathematician), Non-surveyable proof, Notices of the American Mathematical Society, NP-completeness, Orientability, Paul Seymour (mathematician), Percy John Heawood, Peter Tait (physicist), Philip Franklin, Planar graph, Proof assistant, Quartic function, Robin Thomas (mathematician), RWTH Aachen University, Snark (graph theory), Szilassi polyhedron, The Athenaeum (British magazine), The Mathematical Intelligencer, The New York Times, Theorem, Time complexity, Toroidal polyhedron, Torus, Transitive relation, Triangle-free graph, Triangulation (geometry), University College London, University of Illinois at Urbana–Champaign, Upper Peninsula of Michigan, Vertex (graph theory), W. W. Rouse Ball, Wolfgang Haken, 1-planar graph. 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.

New!!: Four color theorem and Alfred Kempe · See more »

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.

New!!: Four color theorem and Apollonian network · See more »

Augustus De Morgan

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

New!!: Four color theorem and Augustus De Morgan · See more »

Azerbaijan

No description.

New!!: Four color theorem and Azerbaijan · See more »

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.

New!!: Four color theorem and Big O notation · See more »

Cartography

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

New!!: Four color theorem and Cartography · See more »

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.

New!!: Four color theorem and Compactness theorem · See more »

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.

New!!: Four color theorem and Computational complexity theory · See more »

Computer-assisted proof

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

New!!: Four color theorem and Computer-assisted proof · See more »

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.

New!!: Four color theorem and Connected space · See more »

Coq

In computer science, Coq is an interactive theorem prover.

New!!: Four color theorem and Coq · See more »

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.

New!!: Four color theorem and Cuboid · See more »

Daniel P. Sanders

Daniel P. Sanders is an American mathematician.

New!!: Four color theorem and Daniel P. Sanders · See more »

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

New!!: Four color theorem and De Bruijn–Erdős theorem (graph theory) · See more »

Discharging method (discrete mathematics)

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

New!!: Four color theorem and Discharging method (discrete mathematics) · See more »

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.

New!!: Four color theorem and Discrete Mathematics (journal) · See more »

Dorothea Blostein

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

New!!: Four color theorem and Dorothea Blostein · See more »

Dror Bar-Natan

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

New!!: Four color theorem and Dror Bar-Natan · See more »

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.

New!!: Four color theorem and Enclave and exclave · See more »

Euler characteristic

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

New!!: Four color theorem and Euler characteristic · See more »

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.

New!!: Four color theorem and Finite type invariant · See more »

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.

New!!: Four color theorem and First-order logic · See more »

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.

New!!: Four color theorem and Five color theorem · See more »

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

New!!: Four color theorem and Floor and ceiling functions · See more »

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.

New!!: Four color theorem and Francis Guthrie · See more »

Genus (mathematics)

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

New!!: Four color theorem and Genus (mathematics) · See more »

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.

New!!: Four color theorem and Geographic contiguity · See more »

Georges Gonthier

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

New!!: Four color theorem and Georges Gonthier · See more »

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.

New!!: Four color theorem and Gerhard Ringel · See more »

German Mathematical Society

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

New!!: Four color theorem and German Mathematical Society · See more »

Glossary of graph theory terms

This is a glossary of graph theory terms.

New!!: Four color theorem and Glossary of graph theory terms · See more »

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".

New!!: Four color theorem and Graph (discrete mathematics) · See more »

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.

New!!: Four color theorem and Graph coloring · See more »

Graph theory

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

New!!: Four color theorem and Graph theory · See more »

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.

New!!: Four color theorem and Grötzsch's theorem · See more »

Hadwiger conjecture (graph theory)

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.

New!!: Four color theorem and Hadwiger conjecture (graph theory) · See more »

Hadwiger–Nelson problem

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.

New!!: Four color theorem and Hadwiger–Nelson problem · See more »

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.

New!!: Four color theorem and Heawood conjecture · See more »

Heinrich Heesch

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

New!!: Four color theorem and Heinrich Heesch · See more »

Hugo Hadwiger

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

New!!: Four color theorem and Hugo Hadwiger · See more »

Immersion (mathematics)

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

New!!: Four color theorem and Immersion (mathematics) · See more »

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.

New!!: Four color theorem and John William Theodore Youngs · See more »

Julius Petersen

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

New!!: Four color theorem and Julius Petersen · See more »

Kaliningrad Oblast

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.

New!!: Four color theorem and Kaliningrad Oblast · See more »

Kempe chain

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

New!!: Four color theorem and Kempe chain · See more »

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.

New!!: Four color theorem and Kenneth Appel · See more »

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.

New!!: Four color theorem and Kenneth O. May · See more »

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.

New!!: Four color theorem and Klein bottle · See more »

Kurt Gödel

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

New!!: Four color theorem and Kurt Gödel · See more »

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.

New!!: Four color theorem and Lie algebra · See more »

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.

New!!: Four color theorem and Lower Peninsula of Michigan · See more »

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.

New!!: Four color theorem and MacTutor History of Mathematics archive · See more »

Map coloring

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

New!!: Four color theorem and Map coloring · See more »

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.

New!!: Four color theorem and Masterpiece · See more »

Mathematics

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

New!!: Four color theorem and Mathematics · See more »

MathOverflow

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

New!!: Four color theorem and MathOverflow · See more »

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.

New!!: Four color theorem and Möbius strip · See more »

Microform

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

New!!: Four color theorem and Microform · See more »

Nakhchivan Autonomous Republic

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

New!!: Four color theorem and Nakhchivan Autonomous Republic · See more »

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.

New!!: Four color theorem and Neil Robertson (mathematician) · See more »

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.

New!!: Four color theorem and Non-surveyable proof · See more »

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.

New!!: Four color theorem and Notices of the American Mathematical Society · See more »

NP-completeness

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

New!!: Four color theorem and NP-completeness · See more »

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.

New!!: Four color theorem and Orientability · See more »

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.

New!!: Four color theorem and Paul Seymour (mathematician) · See more »

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.

New!!: Four color theorem and Percy John Heawood · See more »

Peter Tait (physicist)

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

New!!: Four color theorem and Peter Tait (physicist) · See more »

Philip Franklin

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

New!!: Four color theorem and Philip Franklin · See more »

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.

New!!: Four color theorem and Planar graph · See more »

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.

New!!: Four color theorem and Proof assistant · See more »

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.

New!!: Four color theorem and Quartic function · See more »

Robin Thomas (mathematician)

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

New!!: Four color theorem and Robin Thomas (mathematician) · See more »

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".

New!!: Four color theorem and RWTH Aachen University · See more »

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.

New!!: Four color theorem and Snark (graph theory) · See more »

Szilassi polyhedron

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

New!!: Four color theorem and Szilassi polyhedron · See more »

The Athenaeum (British magazine)

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

New!!: Four color theorem and The Athenaeum (British magazine) · See more »

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.

New!!: Four color theorem and The Mathematical Intelligencer · See more »

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.

New!!: Four color theorem and The New York Times · See more »

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.

New!!: Four color theorem and Theorem · See more »

Time complexity

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

New!!: Four color theorem and Time complexity · See more »

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.

New!!: Four color theorem and Toroidal polyhedron · See more »

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.

New!!: Four color theorem and Torus · See more »

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.

New!!: Four color theorem and Transitive relation · See more »

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.

New!!: Four color theorem and Triangle-free graph · See more »

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.

New!!: Four color theorem and Triangulation (geometry) · See more »

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.

New!!: Four color theorem and University College London · See more »

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.

New!!: Four color theorem and University of Illinois at Urbana–Champaign · See more »

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.

New!!: Four color theorem and Upper Peninsula of Michigan · See more »

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

New!!: Four color theorem and Vertex (graph theory) · See more »

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.

New!!: Four color theorem and W. W. Rouse Ball · See more »

Wolfgang Haken

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

New!!: Four color theorem and Wolfgang Haken · See more »

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.

New!!: Four color theorem and 1-planar graph · See more »

Redirects here:

4 color map problem, 4 color problem, 4 color theorem, 4 colour map problem, 4 colour theorem, 4-color conjecture, 4-color problem, 4-color theorem, 4-colors theorem, 4CT, Four Color Conjecture, Four Color Problem, Four Color Theorem, Four Color Theory, Four Colour Theorem, Four color conjecture, Four color map problem, Four color map theorem, Four color problem, Four colour map problem, Four colour problem, Four colour theorem, Four-Color Maps, Four-Color Theorem, Four-Colour Map Problem, Four-Colour Theorem, Four-color conjecture, Four-color map, Four-color map problem, Four-color map theorem, Four-color problem, Four-color theorem, Four-colour Theorem, Four-colour map, Four-colour map problem, Four-colour problem, Four-colour theorem, History of the four color theorem, Map color problem, Map coloring problem, Map-coloring problem, Minimum number of map colors, Proof of the 4 color theorem, Seven colour theorem, The Four-Color map Theorem.

References

[1] https://en.wikipedia.org/wiki/Four_color_theorem

OutgoingIncoming
Hey! We are on Facebook now! »