Heawood conjecture

Last updated

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. For surfaces of genus 0, 1, 2, 3, 4, 5, 6, 7, ..., the required number of colors is 4, 7, 8, 9, 10, 11, 12, 12, .... OEIS:  A000934 , the chromatic number or Heawood number.

Graph theory study of graphs, which are mathematical structures used to model pairwise relations between objects

In mathematics, graph theory is the study of graphs, which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of vertices which are connected by edges. A distinction is made between undirected graphs, where edges link two vertices symmetrically, and directed graphs, where edges, then called arrows, link two vertices asymmetrically; see Graph for more detailed definitions and for other variations in the types of graph that are commonly considered. Graphs are one of the prime objects of study in discrete mathematics.

Graph coloring assignment of labels traditionally called "colors" to elements of a graph

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 its simplest form, it is a way of coloring the vertices of a graph such that no two adjacent vertices are of the same color; this is called a vertex coloring. Similarly, an edge coloring assigns a color to each edge so that no two adjacent edges are of the same color, and a face coloring of a planar graph assigns a color to each face or region so that no two faces that share a boundary have the same color.

Surface (topology) two-dimensional manifold, and, as such, may be an "abstract surface" not embedded in any Euclidean space

In topology, a surface is a two-dimensional manifold. Some surfaces arise as the boundaries of three-dimensional solids; for example, the sphere is the boundary of the solid ball. Other surfaces arise as graphs of functions of two variables; see the figure at right. However, surfaces can also be defined abstractly, without reference to any ambient space. For example, the Klein bottle is a surface that cannot be embedded in three-dimensional Euclidean space.

Contents

The conjecture was formulated in 1890 by Percy John Heawood and proven in 1968 by Gerhard Ringel and Ted Youngs. One case, the non-orientable Klein bottle, proved an exception to the general formula. An entirely different approach was needed for the much older problem of finding the number of colors needed for the plane or sphere, solved in 1976 as the four color theorem by Haken and Appel. On the sphere the lower bound is easy, whereas for higher genera the upper bound is easy and was proved in Heawood's original short paper that contained the conjecture. In other words, Ringel, Youngs and others had to construct extreme examples for every genus g = 1,2,3,.... If g = 12s + k, the genera fall into 12 cases according as k = 0,1,2,3,4,5,6,7,8,9,10,11. To simplify, suppose that case k has been established if only a finite number of g's of the form 12s + k are in doubt. Then the years in which the twelve cases were settled and by whom are the following:

Percy John Heawood British mathematician

Percy John Heawood was a British mathematician educated at Queen Elizabeth's School, Ipswich, and Exeter College, Oxford. He spent his career at Durham University, where he was appointed Lecturer in 1885. He was, successively, Censor of St Cuthbert's Society between 1897 and 1901 succeeding Frank Byron Jevons in the role, Senior Proctor of the university from 1901, Professor in 1910 and Vice-Chancellor between 1926 and 1928. He was awarded an OBE, as Honorary Secretary of the Preservation Fund, for his part in raising £120,000 to prevent Durham Castle from collapsing into the River Wear.

Gerhard Ringel German-American mathematician

Gerhard Ringel was a German mathematician who earned his Ph.D. from the University of Bonn in 1951. He was one of the pioneers in graph theory and contributed significantly to the proof of the Heawood conjecture, a mathematical problem closely linked with the Four Color Theorem.

John William Theodore Youngs was an American mathematician.

The last seven sporadic exceptions were settled as follows:

Formal statement

The Franklin graph. Franklin graph.svg
The Franklin graph.

Percy John 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

Conjecture proposition in mathematics that is unproven

In mathematics, a conjecture is a conclusion or proposition based on incomplete information, for which no proof has been found. Conjectures such as the Riemann hypothesis or Fermat's Last Theorem have shaped much of mathematical history as new areas of mathematics are developed in order to prove them.

where is the floor function.

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

In mathematics, and more specifically in algebraic topology and polyhedral combinatorics, the Euler characteristic is a topological invariant, a number that describes a topological space's shape or structure regardless of the way it is bent. It is commonly denoted by .

This relation holds, as Ringel and Youngs showed, for all surfaces except for the Klein bottle. Philip Franklin (1930) proved that the Klein bottle requires at most 6 colors, rather than 7 as predicted by the formula. The Franklin graph can be drawn on the Klein bottle in a way that forms six mutually-adjacent regions, showing that this bound is tight.

Klein bottle A type of non-orientable surface

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. Informally, it is a one-sided surface which, if traveled upon, could be followed back to the point of origin while flipping the traveler upside down. Other related non-orientable objects include the Möbius strip and the real projective plane. Whereas a Möbius strip is a surface with boundary, a Klein bottle has no boundary.

Philip Franklin was an American mathematician and professor whose work was primarily focused in analysis.

Franklin graph

In the mathematical field of graph theory, the Franklin graph a 3-regular graph with 12 vertices and 18 edges.

The upper bound, proved in Heawood's original short paper, is based on a greedy coloring algorithm. By manipulating the Euler characteristic, one can show that every graph embedded in the given 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.

Example

A partition of the torus into seven mutually adjacent regions, requiring seven colors. 7x-torus.svg
A partition of the torus into seven mutually adjacent regions, requiring seven colors.

The torus has g = 1, so χ = 0. 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.

Related Research Articles

Four color theorem statement in mathematics

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. Adjacent means that two regions share a common boundary curve segment, not merely a corner where three or more regions meet. It was the first major theorem to be proved using a computer. Initially, this proof was not accepted by all mathematicians because the computer-assisted proof was infeasible for a human to check by hand. Since then the proof has gained wide acceptance, although some doubters remain.

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 other words, it can be drawn in such a way that no edges cross each other. Such a drawing is called a plane graph or planar embedding of the graph. A plane graph can be defined as a planar graph with a mapping from every node to a point on a plane, and from every edge to a plane curve on that plane, such that the extreme points of each curve are the points mapped from its end nodes, and all curves are disjoint except on their extreme points.

Turán graph graph

The Turán graphT(n,r) is a complete multipartite graph formed by partitioning a set of n vertices into r subsets, with sizes as equal as possible, and connecting two vertices by an edge if and only if they belong to different subsets. The graph will have subsets of size , and subsets of size . That is, it is a complete r-partite graph

Edge coloring an assignment of colors to the edges of a graph so that no two edges that share an endpoint have the same color as each other

In graph theory, an edge coloring of a graph is an assignment of "colors" to the edges of the graph so that no two incident edges have the same color. For example, the figure to the right shows an edge coloring of a graph by the colors red, blue, and green. Edge colorings are one of several different types of graph coloring. The edge-coloring problem asks whether it is possible to color the edges of a given graph using at most k different colors, for a given value of k, or with the fewest possible colors. The minimum required number of colors for the edges of a given graph is called the chromatic index of the graph. For example, the edges of the graph in the illustration can be colored by three colors but cannot be colored by two colors, so the graph shown has chromatic index three.

Total coloring

In graph theory, total coloring is a type of graph coloring on the vertices and edges of a graph. When used without any qualification, a total coloring is always assumed to be proper in the sense that no adjacent edges and no edge and its endvertices are assigned the same color. The total chromatic number χ″(G) of a graph G is the least number of colors needed in any total coloring of G.

Heawood graph undirected graph with 14 vertices, 21 edges, and girth 6

In the mathematical field of graph theory, the Heawood graph is an undirected graph with 14 vertices and 21 edges, named after Percy John Heawood.

The art gallery problem or museum problem is a well-studied visibility problem in computational geometry. It originates from a real-world problem of guarding an art gallery with the minimum number of guards who together can observe the whole gallery. In the geometric version of the problem, the layout of the art gallery is represented by a simple polygon and each guard is represented by a point in the polygon. A set of points is said to guard a polygon if, for every point in the polygon, there is some such that the line segment between and does not leave the polygon.

Hadwiger conjecture (graph theory) conjecture that all graphs requiring k or more colors contain a k-vertex complete minor

In graph theory, the Hadwiger 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. Contracting the edges within each of these subgraphs so that each subgraph collapses to a single vertex produces a complete graph Kk on k vertices as a minor of G.

Heawood number

In mathematics, the Heawood number of a surface is a certain upper bound for the maximal number of colors needed to color any graph embedded in the surface.

In mathematics, the Cheeger constant of a graph is a numerical measure of whether or not a graph has a "bottleneck". The Cheeger constant as a measure of "bottleneckedness" is of great interest in many areas: for example, constructing well-connected networks of computers, card shuffling. The graph theoretical notion originated after the Cheeger isoperimetric constant of a compact Riemannian manifold.

In graph theory, oriented graph coloring is a special type of graph coloring. Namely, it is an assignment of colors to vertices of an oriented graph that

Crossing number (graph theory) the smallest number of edge crossings possible in a drawing of a node-link graph

In graph theory, the crossing numbercr(G) of a graph G is the lowest number of edge crossings of a plane drawing of the graph G. For instance, a graph is planar if and only if its crossing number is zero. Determining the crossing number continues to be of great importance in graph drawing, as user studies have shown that drawing graphs with few crossings makes it easier for people to understand the drawing.

Turáns brick factory problem

In the mathematics of graph drawing, Turán's brick factory problem asks for the minimum number of crossings in a drawing of a complete bipartite graph. The problem is named after Pál Turán, who formulated it while being forced to work in a brick factory during World War II.

In combinatorial mathematics, the Albertson conjecture is an unproven relationship between the crossing number and the chromatic number of a graph. It is named after Michael O. Albertson, a professor at Smith College, who stated it as a conjecture in 2007; it is one of his many conjectures in graph coloring theory. The conjecture states that, among all graphs requiring n colors, the complete graph Kn is the one with the smallest crossing number. Equivalently, if a graph can be drawn with fewer crossings than Kn, then, according to the conjecture, it may be colored with fewer than n colors.

The graph coloring game is a mathematical game related to graph theory. Coloring game problems arose as game-theoretic versions of well-known graph coloring problems. In a coloring game, two players use a given set of colors to construct a coloring of a graph, following specific rules depending on the game we consider. One player tries to successfully complete the coloring of the graph, when the other one tries to prevent him from achieving it.

Penny graph contact graph of unit circles

In geometric graph theory, a penny graph is a contact graph of unit circles. That is, it is an undirected graph whose vertices can be represented by unit circles, with no two of these circles crossing each other, and with two adjacent vertices if and only if they are represented by tangent circles. More simply, they are the graphs formed by arranging pennies in a non-overlapping way on a flat surface, making a vertex for each penny, and making an edge for each two pennies that touch.

References