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) » « Shrink index
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.
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 (27 June 1806 – 18 March 1871) was a British mathematician and logician.
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 (from Greek χάρτης chartēs, "papyrus, sheet of paper, map"; and γράφειν graphein, "write") is the study and practice of making maps.
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 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.
A computer-assisted proof is a mathematical proof that has been at least partially generated by computer.
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.
In computer science, Coq is an interactive theorem prover.
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 is an American mathematician.
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).
The discharging method is a technique used to prove lemmas in structural graph theory.
Discrete Mathematics is a biweekly peer-reviewed scientific journal in the broad area of discrete mathematics, combinatorics, graph theory, and their applications.
Dorothea Haken Blostein is a Canadian computer scientist who works as a professor of computer science at Queen's University.
Dror Bar-Natan (דרוֹר בָר-נָתָן; born January 30, 1966) is a Professor at the University of Toronto Department of Mathematics, Canada.
An enclave is a territory, or a part of a territory, that is entirely surrounded by the territory of one other state.
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.
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—also known as first-order predicate calculus and predicate logic—is a collection of formal systems used in mathematics, philosophy, linguistics, and computer science.
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.
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 (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.
In mathematics, genus (plural genera) has a few different, but closely related, meanings.
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 is one of the leading practitioners in formal mathematics.
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.
The German Mathematical Society (Deutsche Mathematiker-Vereinigung – DMV) is the main professional society of German mathematicians.
This is a glossary of graph theory terms.
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".
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.
In mathematics, graph theory is the study of graphs, which are mathematical structures used to model pairwise relations between objects.
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.
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 (June 25, 1906 – July 26, 1995) was a German mathematician.
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.
In mathematics, an immersion is a differentiable function between differentiable manifolds whose derivative is everywhere injective.
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 Peter Christian Petersen (16 June 1839, Sorø, West Zealand – 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.
In mathematics, a Kempe chain is a device used mainly in the study of the four colour theorem.
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 (July 8, 1915, in Portland, Oregon – December 1977, in Toronto) was an American mathematician and historian of mathematics, who developed May's theorem.
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 Friedrich Gödel (April 28, 1906 – January 14, 1978) was an Austrian, and later American, logician, mathematician, and philosopher.
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.
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.
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 is the act of assigning different colors to different features on a map.
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 (from Greek μάθημα máthēma, "knowledge, study, learning") is the study of such topics as quantity, structure, space, and change.
MathOverflow is a mathematics website, which serves both as a collaborative blog and an online community of mathematicians.
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.
Microforms are scaled-down reproductions of documents, typically either films or paper, made for the purposes of transmission, storage, reading, and printing.
The Nakhchivan Autonomous Republic (Naxçıvan Muxtar Respublikası) is a landlocked exclave of the Republic of Azerbaijan.
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.
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 is the membership journal of the American Mathematical Society (AMS), published monthly except for the combined June/July issue.
In computational complexity theory, an NP-complete decision problem is one belonging to both the NP and the NP-hard complexity classes.
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 (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 (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 Guthrie Tait FRSE (28 April 1831 – 4 July 1901) was a Scottish mathematical physicist and early pioneer in thermodynamics.
Philip Franklin (October 5, 1898 – January 27, 1965) was an American mathematician and professor whose work was primarily focused in analysis.
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.
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.
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 is a mathematician working in graph theory at the Georgia Institute of Technology.
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".
In the mathematical field of graph theory, a snark is a simple, connected, bridgeless cubic graph with chromatic index equal to 4.
The Szilassi polyhedron is a nonconvex polyhedron, topologically a torus, with seven hexagonal faces.
The Athenaeum was a literary magazine published in London, England from 1828 to 1921.
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 (sometimes abbreviated as The NYT or The Times) is an American newspaper based in New York City with worldwide influence and readership.
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.
In computer science, the time complexity is the computational complexity that describes the amount of time it takes to run an algorithm.
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.
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.
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.
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.
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 (UCL) is a public research university in London, England, and a constituent college of the federal University of London.
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.
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.
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).
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 (born June 21, 1928 in Berlin, Germany) is a mathematician who specializes in topology, in particular 3-manifolds.
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.
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.