HOME

TheInfoList



OR:

In
graph theory 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'' (also called ''nodes'' or ''points'') which are conn ...
, Vizing's theorem states that every simple
undirected graph In discrete 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". The objects correspond to mathematical abstractions called '' v ...
may be edge colored using a number of colors that is at most one larger than the maximum
degree Degree may refer to: As a unit of measurement * Degree (angle), a unit of angle measurement ** Degree of geographical latitude ** Degree of geographical longitude * Degree symbol (°), a notation used in science, engineering, and mathemati ...
of the graph. At least colors are always necessary, so the undirected graphs may be partitioned into two classes: "class one" graphs for which colors suffice, and "class two" graphs for which colors are necessary. A more general version of Vizing's theorem states that every undirected
multigraph In mathematics, and more specifically in graph theory, a multigraph is a graph which is permitted to have multiple edges (also called ''parallel edges''), that is, edges that have the same end nodes. Thus two vertices may be connected by mo ...
without loops can be colored with at most colors, where is the multiplicity of the multigraph. The theorem is named for
Vadim G. Vizing Vadim Georgievich Vizing (russian: Вади́м Гео́ргиевич Визинг, uk, Вадим Георгійович Візінг; 25 March 1937 – 23 August 2017) was a Soviet and Ukrainian mathematician known for his contributions to grap ...
who published it in 1964.


Discovery

The theorem discovered by Russian mathematician
Vadim G. Vizing Vadim Georgievich Vizing (russian: Вади́м Гео́ргиевич Визинг, uk, Вадим Георгійович Візінг; 25 March 1937 – 23 August 2017) was a Soviet and Ukrainian mathematician known for his contributions to grap ...
was published in 1964 when Vizing was working in
Novosibirsk Novosibirsk (, also ; rus, Новосиби́рск, p=nəvəsʲɪˈbʲirsk, a=ru-Новосибирск.ogg) is the largest city and administrative centre of Novosibirsk Oblast and Siberian Federal District in Russia. As of the 2021 Census, ...
and became known as Vizing's theorem. Indian mathematician R. P. Gupta independently discovered the theorem, while undertaking his doctorate (1965-1967).


Examples

When , the graph must itself be a matching, with no two edges adjacent, and its edge chromatic number is one. That is, all graphs with are of class one. When , the graph must be a
disjoint union In mathematics, a disjoint union (or discriminated union) of a family of sets (A_i : i\in I) is a set A, often denoted by \bigsqcup_ A_i, with an injection of each A_i into A, such that the images of these injections form a partition of A ...
of paths and cycles. If all cycles are even, they can be 2-edge-colored by alternating the two colors around each cycle. However, if there exists at least one odd cycle, then no 2-edge-coloring is possible. That is, a graph with is of class one if and only if it is bipartite.


Proof

This proof is inspired by . Let be a simple undirected graph. We proceed by induction on , the number of edges. If the graph is empty, the theorem trivially holds. Let and suppose a proper -edge-coloring exists for all where . We say that color is missing in with respect to proper -edge-coloring if for all . Also, let -path from denote the unique maximal path starting in with -colored edge and alternating the colors of edges (the second edge has color , the third edge has color and so on), its length can be . Note that if is a proper -edge-coloring of then every vertex has a missing color with respect to . Suppose that no proper -edge-coloring of exists. This is equivalent to this statement: :(1) Let and be arbitrary proper -edge-coloring of and be missing from and be missing from with respect to . Then the -path from ends in . This is equivalent, because if (1) doesn't hold, then we can interchange the colors and on the -path and set the color of to be , thus creating a proper -edge-coloring of from . The other way around, if a proper -edge-coloring exists, then we can delete , restrict the coloring and (1) won't hold either. Now, let and be a proper -edge-coloring of and be missing in with respect to . We define to be a maximal sequence of neighbours of such that is missing in with respect to for all . We define colorings as : for all , : not defined, : otherwise. Then is a proper -edge-coloring of due to definition of . Also, note that the missing colors in are the same with respect to for all . Let be the color missing in with respect to , then is also missing in with respect to for all . Note that cannot be missing in , otherwise we could easily extend , therefore an edge with color is incident to for all . From the maximality of , there exists such that . From the definition of this holds: : Let be the -path from with respect to . From (1), has to end in . But is missing in , so it has to end with an edge of color . Therefore, the last edge of is . Now, let be the -path from with respect to . Since is uniquely determined and the inner edges of are not changed in , the path uses the same edges as in reverse order and visits . The edge leading to clearly has color . But is missing in , so ends in . Which is a contradiction with (1) above.


Classification of graphs

Several authors have provided additional conditions that classify some graphs as being of class one or class two, but do not provide a complete classification. For instance, if the vertices of the maximum degree in a graph form an independent set, or more generally if the
induced subgraph In the mathematical field of graph theory, an induced subgraph of a graph is another graph, formed from a subset of the vertices of the graph and ''all'' of the edges (from the original graph) connecting pairs of vertices in that subset. Definit ...
for this set of vertices is a forest, then must be of class one. showed that
almost all In mathematics, the term "almost all" means "all but a negligible amount". More precisely, if X is a set, "almost all elements of X" means "all elements of X but those in a negligible subset of X". The meaning of "negligible" depends on the mathem ...
graphs are of class one. That is, in the
Erdős–Rényi model In the mathematical field of graph theory, the Erdős–Rényi model is either of two closely related models for generating random graphs or the evolution of a random network. They are named after Hungarian mathematicians Paul Erdős and Alf ...
of random graphs, in which all -vertex graphs are equally likely, let be the probability that an -vertex graph drawn from this distribution is of class one; then approaches one in the limit as goes to infinity. For more precise bounds on the rate at which converges to one, see .


Planar graphs

showed that a
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. In other words, it can be drawn in such a way that no edges cro ...
is of class one if its maximum degree is at least eight. In contrast, he observed that for any maximum degree in the range from two to five, there exist planar graphs of class two. For degree two, any odd cycle is such a graph, and for degree three, four, and five, these graphs can be constructed from
platonic solid In geometry, a Platonic solid is a convex, regular polyhedron in three-dimensional Euclidean space. Being a regular polyhedron means that the faces are congruent (identical in shape and size) regular polygons (all angles congruent and all e ...
s by replacing a single edge by a path of two adjacent edges. In Vizing's planar graph conjecture, states that all simple, planar graphs with maximum degree six or seven are of class one, closing the remaining possible cases. Independently, and partially proved Vizing's planar graph conjecture by showing that all planar graphs with maximum degree seven are of class one. Thus, the only case of the conjecture that remains unsolved is that of maximum degree six. This conjecture has implications for the total coloring conjecture. The planar graphs of class two constructed by subdivision of the platonic solids are not regular: they have vertices of degree two as well as vertices of higher degree. The
four color theorem In mathematics, the four color theorem, or the four color map theorem, states that no more than four colors are required to color the regions of any map so that no two adjacent regions have the same color. ''Adjacent'' means that two regions sh ...
(proved by ) on vertex coloring of planar graphs, is equivalent to the statement that every bridgeless 3-regular planar graph is of class one .


Graphs on nonplanar surfaces

In 1969,
Branko Grünbaum Branko Grünbaum ( he, ברנקו גרונבאום; 2 October 1929 – 14 September 2018) was a Croatian-born mathematician of Jewish descentoriented manifold In mathematics, orientability is a property of some topological spaces such as real vector spaces, Euclidean spaces, surfaces, and more generally manifolds that allows a consistent definition of "clockwise" and "counterclockwise". A space is ...
such as a
torus In geometry, a torus (plural tori, colloquially donut or doughnut) is a surface of revolution generated by revolving a circle in three-dimensional space about an axis that is coplanar with the circle. If the axis of revolution does not ...
must be of class one. In this context, a polyhedral embedding is a
graph embedding In topological graph theory, an embedding (also spelled imbedding) of a graph G on a surface \Sigma is a representation of G on \Sigma in which points of \Sigma are associated with vertices and simple arcs ( homeomorphic images of ,1/math> ...
such that every face of the embedding is topologically a disk and such that the
dual graph In the mathematical discipline of graph theory, the dual graph of a plane graph is a graph that has a vertex for each face of . The dual graph has an edge for each pair of faces in that are separated from each other by an edge, and a self-loo ...
of the embedding is simple, with no self-loops or multiple adjacencies. If true, this would be a generalization of the four color theorem, which was shown by Tait to be equivalent to the statement that 3-regular graphs with a polyhedral embedding on a
sphere A sphere () is a Geometry, geometrical object that is a solid geometry, three-dimensional analogue to a two-dimensional circle. A sphere is the Locus (mathematics), set of points that are all at the same distance from a given point in three ...
are of class one. However, showed the conjecture to be false by finding snarks that have polyhedral embeddings on high-genus orientable surfaces. Based on this construction, he also showed that it is NP-complete to tell whether a polyhedrally embedded graph is of class one.


Algorithms

describe a polynomial time algorithm for coloring the edges of any graph with colors, where is the maximum degree of the graph. That is, the algorithm uses the optimal number of colors for graphs of class two, and uses at most one more color than necessary for all graphs. Their algorithm follows the same strategy as Vizing's original proof of his theorem: it starts with an uncolored graph, and then repeatedly finds a way of recoloring the graph in order to increase the number of colored edges by one. More specifically, suppose that is an uncolored edge in a partially colored graph. The algorithm of Misra and Gries may be interpreted as constructing a directed
pseudoforest In graph theory, a pseudoforest is an undirected graphThe kind of undirected graph considered here is often called a multigraph or pseudograph, to distinguish it from a simple graph. in which every connected component has at most one cycle. Tha ...
(a graph in which each vertex has at most one outgoing edge) on the neighbors of : for each neighbor of , the algorithm finds a color that is not used by any of the edges incident to , finds the vertex (if it exists) for which edge has color , and adds as an edge to . There are two cases: *If the pseudoforest constructed in this way contains a path from to a vertex that has no outgoing edges in , then there is a color that is available both at and . Recoloring edge with color allows the remaining edge colors to be shifted one step along this path: for each vertex in the path, edge takes the color that was previously used by the successor of in the path. This leads to a new coloring that includes edge . *If, on the other hand, the path starting from in the pseudoforest leads to a cycle, let be the neighbor of at which the path joins the cycle, let be the color of edge , and let be a color that is not used by any of the edges at vertex . Then swapping colors and on a Kempe chain either breaks the cycle or the edge on which the path joins the cycle, leading to the previous case. With some simple data structures to keep track of the colors that are used and available at each vertex, the construction of and the recoloring steps of the algorithm can all be implemented in time , where is the number of vertices in the input graph. Since these steps need to be repeated times, with each repetition increasing the number of colored edges by one, the total time is . In an unpublished technical report, claimed a faster O(m\sqrt n\log n) time bound for the same problem of coloring with colors.


History

In both and , Vizing mentions that his work was motivated by a theorem of showing that multigraphs could be colored with at most colors. Although Vizing's theorem is now standard material in many graph theory textbooks, Vizing had trouble publishing the result initially, and his paper on it appears in an obscure journal, ''Diskret. Analiz''.The full name of this journal was ''Akademiya Nauk SSSR. Sibirskoe Otdelenie. Institut Matematiki. Diskretny˘ı Analiz. Sbornik Trudov''. It was renamed ''Metody Diskretnogo Analiza'' in 1980 (the name given for it in ) and discontinued in 199


See also

*
Brooks' theorem In graph theory, Brooks' theorem states a relationship between the maximum degree of a graph and its chromatic number. According to the theorem, in a connected graph in which every vertex has at most Δ neighbors, the vertices can be colored with o ...
relating vertex colorings to maximum degree


Notes


References

*. *. *. *. *. *. *. *. *. *. *. *. *. *. *. *. (In Russian.) *{{citation , last = Zhang , first1 = Limin, year = 2000 , title = Every planar graph with maximum degree 7 is of class 1 , journal =
Graphs and Combinatorics ''Graphs and Combinatorics'' (ISSN 0911-0119, abbreviated ''Graphs Combin.'') is a peer-reviewed academic journal in graph theory, combinatorics, and discrete geometry published by Springer Japan. Its editor-in-chief is Katsuhiro Ota of Keio Unive ...
, volume = 16 , issue = 4 , pages = 467–495.


External links


Proof of Vizing's theorem
at
PlanetMath PlanetMath is a free, collaborative, mathematics online encyclopedia. The emphasis is on rigour, openness, pedagogy, real-time content, interlinked content, and also community of about 24,000 people with various maths interests. Intended to be c ...
. Graph coloring Theorems in graph theory