Vizing theorem

Vizing's theorem is a statement of graph theory , according to which the edges of any simple non-oriented graph can be painted in a number of colors, maximum one greater than the maximum degree of vertices $\delta$ ${\ displaystyle \ delta}$ $\ delta$ count. Since at least $\delta$ ${\ displaystyle \ delta}$ $\ delta$ colors are always necessary, all undirected graphs can be divided into two classes - “first class” columns, for which $\delta$ ${\ displaystyle \ delta}$ $\ delta$ there are enough colors and “second class” for which $\delta +1$ ${\ displaystyle \ delta +1}$ $\ delta +1$ colors.

The result was established by Vadim Vizing in 1964 .

Content

Examples

If a $\delta =1$ ${\ displaystyle \ delta = 1}$ in the box $G$ ${\ displaystyle G}$ there are no adjacent edges, and the edges can be painted in one color. Thus, all graphs with $\delta (G)=1$ ${\ displaystyle \ delta (G) = 1}$ belongs to the first class.

If a $\delta =2$ ${\ displaystyle \ delta = 2}$ count $G$ ${\ displaystyle G}$ must be a disjoint union of paths and cycles . If all the cycles are even, their edges can be colored in two colors, alternating colors, passing along each cycle. However, if there is at least one odd cycle, its edges cannot be painted in 2 colors. So the graph with $\delta =2$ ${\ displaystyle \ delta = 2}$ belongs to the first class if and only if he is bipartite .

For multigraphs , in general, the Wising theorem is not satisfied. For example, a multigraph formed by doubling each edge of a triangle has a maximum degree of four, but the edges of this graph cannot be painted in less than six colors.

Graph classification

Some authors gave additional conditions for belonging of some graphs to the first or second class, but there is no complete classification. For example, if the vertices of the maximum degree $\delta$ ${\ displaystyle \ delta}$ in the graph $G$ ${\ displaystyle G}$ form an independent set , or, more generally, if the generated subgraph for this set of vertices is a forest, then $G$ ${\ displaystyle G}$ will belong to the first class ^[1] .

Erdёs and Wilson ^[2] showed that almost all graphs belong to the first class. Thus, in the model of random graphs of Erdös, Rényi , in which all graphs with $n$ ${\ displaystyle n}$ vertices are equally likely, let $p(n)$ ${\ displaystyle p (n)}$ denotes the probability that a graph with $n$ ${\ displaystyle n}$ vertices belongs to the first class. Then $p(n)$ ${\ displaystyle p (n)}$ tends to unit aspirations $n$ ${\ displaystyle n}$ to infinity. Later developed more subtle estimates of the rate of aspiration $p(n)$ ${\ displaystyle p (n)}$ to the unit ^[3] .

Flat graphs

Vizing ^[4] showed that a planar graph belongs to the first class if its maximum degree is at least eight. However, he noted that for the maximum degree from two to five, there are planar graphs of the second class. For degree two, any odd cycle is such a graph, and for degrees three, four, and five, such graphs can be constructed from regular polyhedra by replacing edges with paths from pairs of adjacent edges.

Wying's hypothesis about planar graphs ^[4] states that all simple planar graphs with a maximum degree of six and seven belong to the first class, which closes the remaining possibilities. In 2001 ^{[5] it was} established that all planar graphs with a maximum degree of seven belong to the first class. Thus, only the case with the maximum degree of six is questionable. This hypothesis gives the prerequisites for the total coloring hypothesis .

Planar graphs of the second class, constructed from regular polyhedra by splitting edges, are not regular - they have both vertices of the second order and vertices of higher orders. The four-color theorem on coloring the vertices of a planar graph is equivalent to the statement that any 3-regular graph without bridges belongs to the first class ^[6] (this statement is true in view of the proof of the four-color theorem).

Counts on surfaces other than planes

In 1969, Branko Grünbaum hypothesized that any 3-regular graph that has an embedding in the form of a polyhedron in any two-dimensional oriented manifold , such as a torus , must belong to the first class. In this context, a polyhedron embedding means a graph embedding , in which any obtained face of a graph is topologically equivalent to a disk, and in which the dual graph is simple, without loops or multiple adjacencies. If this were true, this would be a generalization of the four-color theorem, which, as Tate showed, is equivalent to the statement that any 3-regular graph for which there is an embedding in the form of a polyhedron in a sphere belongs to the first class. However, in 2009 ^[7], it was shown that the hypothesis is not true, finding snapshots , which has an attachment in the form of polyhedra in oriented surfaces having a high genus . Based on this construction, he also showed that determining whether a graph with an embedding as a polyhedron belongs to the first class belongs to an NP-complete problem ^[8] .

Algorithms

In 1992 ^[9] a polynomial-time algorithm was described for coloring any graph using $\delta +1$ ${\ displaystyle \ delta +1}$ flowers where $\delta$ ${\ displaystyle \ delta}$ - the maximum degree of the graph. Thus, the algorithm uses the optimal number of colors for graphs of the second class, and uses a maximum of one extra color for all graphs. The algorithm uses the same strategy as the initial proof of Vizing's theorem - the algorithm begins with a graph without colors and consistently searches for ways of coloring, so as to involve another edge in the coloring.

In the description of the algorithm, the terms “fan”, “fan rotation” and “ $c d$ ${\ displaystyle cd}$ -path ", entered by the authors of the algorithm ^[10] , as well as the following agreement: color $d$ ${\ displaystyle d}$ free at the top $w$ ${\ displaystyle w}$ if there are no ribs painted in color $d$ ${\ displaystyle d}$ incident to the top $w$ ${\ displaystyle w}$ . The algorithm performs the following steps:

For each unpainted rib $u$ $v$ {\ displaystyle uv} sequence is plotted in a partially colored graph $⟨$ $v$ $,$ $.$ $.$ $.$ $,$ $l$ $⟩$ {\ displaystyle \ left \ langle v, ..., l \ right \ rangle} - maximum fan.
- For each pair of flowers $c, d$ ${\ displaystyle c, d}$ where $c$ ${\ displaystyle c}$ - color free at the top $u$ ${\ displaystyle u}$ , but $d$ ${\ displaystyle d}$ - color free in $l$ ${\ displaystyle l}$ turn colors $c d$ ${\ displaystyle cd}$ the way.
- Vertex is selected $w$ ${\ displaystyle w}$ so that $\left\langle v,...,w\right\rangle$ ${\ displaystyle \ left \ langle v, ..., w \ right \ rangle}$ is a strap $\left\langle v,...,l\right\rangle$ ${\ displaystyle \ left \ langle v, ..., l \ right \ rangle}$ and $d$ ${\ displaystyle d}$ not used in $w$ ${\ displaystyle w}$ .
- Fan $\left\langle v,...,w\right\rangle$ ${\ displaystyle \ left \ langle v, ..., w \ right \ rangle}$ "Rotates", $u w$ ${\ displaystyle uw}$ painted in color $d$ ${\ displaystyle d}$ .

A fan is a sequence of vertices. $\left\langle v_{0},...,v_{r}\right\rangle$ ${\ displaystyle \ left \ langle v_ {0}, ..., v_ {r} \ right \ rangle}$ with the following properties:

all vertices are vertex neighbors $u$ ${\ displaystyle u}$ and $v_{0}=v$ ${\ displaystyle v_ {0} = v}$
edge $u\,v_{k+1}$ ${\ displaystyle u \, v_ {k + 1}}$ painted in color $d_{k}$ ${\ displaystyle d_ {k}}$ that was not used in vertices $\left\langle v_{0},\ldots ,v_{k}\right\rangle$ ${\ displaystyle \ left \ langle v_ {0}, \ ldots, v_ {k} \ right \ rangle}$

Fan can be rotated , that is, to replace the colors of the ribs $uv_{k}$ ${\ displaystyle uv_ {k}}$ on the colors of the ribs $uv_{k+1}$ ${\ displaystyle uv_ {k + 1}}$ and this rearrangement of colors does not violate the coloring of the graph.

$c d$ ${\ displaystyle cd}$ The path is the maximum sequence of edges starting at $u$ ${\ displaystyle u}$ and each edge is painted $c$ ${\ displaystyle c}$ or $d$ ${\ displaystyle d}$ . Reversing the colors of this chain means replacing $c$ ${\ displaystyle c}$ on $d$ ${\ displaystyle d}$ and $d$ ${\ displaystyle d}$ on $c$ ${\ displaystyle c}$ .

All operations used in the algorithm do not destroy the coloring of the graph, and after inverting the colors $c d$ ${\ displaystyle cd}$ -the path described in the algorithm hook exists.

Using a simple data structure to store the colors used at the top, the entire algorithm step can be completed in time. $O(n)$ ${\ displaystyle O (n)}$ where $n$ ${\ displaystyle n}$ - the number of vertices of the graph. Because every step needs to be repeated for all $m$ ${\ displaystyle m}$ arcs, total time will be $O(mn)$ ${\ displaystyle O (mn)}$ .

In an unpublished paper in 1985 ^[11] , it was argued that it was possible to find a coloring during $O(m{\sqrt {n}}\log n)$ ${\ displaystyle O (m {\ sqrt {n}} \ log n)}$ .

History

It is believed ^[12] ^[13] that Wiesing’s work was inspired by Shannon’s theorem ^[14] , which shows that multigraphs can be colored with no more than ${\tfrac {3}{2}}\delta$ ${\ displaystyle {\ tfrac {3} {2}} \ delta}$ colors. There is also an opinion that Vizing had problems with the publication of the result (first published in the journal Discrete Analysis, published before 1991 by the Institute of Mathematics of the Siberian Branch of the USSR Academy of Sciences , which is called "little known" by Western authors ^[12] ).

Notes

↑ Fournier, 1973 .
↑ Erdős, Wilson, 1977 .
↑ Frieze, Jackson, McDiarmid, Reed, 1988 .
↑ ¹ ² Vizing, 1965 .
↑ Sanders, Zhao, 2001 .
↑ Tait, 1880 .
↑ Kochol, 2009 .
↑ Kochol, 2010 .
↑ Misra, Gries, 1992 .
Алгорит Algorithm description taken from Joachim Breitner article . Proving Vizing's Theorem with Rodin. - 2011.
↑ Gabow et al., 1985 .
↑ ¹ ² Gutin, Toft, 2000 .
↑ Soifer, 2008 .
↑ Shannon, 1949 .

Links

K. Appel, W. Haken. Every planar map is the four colorable // Bulletin of the American Mathematical Society. - 1976. - V. 82 , no. 5 - p . 711–712 . - DOI : 10.1090 / S0002-9904-1976-14122-5 .
Paul Erdős, Robin J. Wilson. Index of almost all graphs // Journal of Combinatorial Theory . - 1977. - Vol. 23 , no. 2–3 . - p . 255–257 . - DOI : 10.1016 / 0095-8956 (77) 90039-9 .
Jean-Claude Fournier. Colorations des arêtes d'un graphe // Cahiers du Center d'Études de Recherche Opérationnelle. - 1973. - T. 15 . - p . 311–314 .
Alan M. Frieze, B. Jackson, CJH McDiarmid, B. Reed. Edge-coloring random graphs // Journal of Combinatorial Theory . - 1988. - V. 45 , no. 2 - pp . 135–149 . - DOI : 10.1016 / 0095-8956 (88) 90065-2 .
Harold N. Gabow, Takao Nishizeki, Oded Kariv, Daniel Leven, Osamu Terada. Algorithms for edge-coloring graphs. - Tohoku University, 1985. - (Tech. Report TRECIS-8501).
Gregory Gutin, Bjarne Toft. Interview with Vadim G. Vizing // European Mathematical Society Newsletter. - 2000. - V. 38 , no. December . - P. 22–23.
Martin Kochol. Proceedings of the American Mathematical Society. - 2009. - T. 137. - p. 1613–1619.
Martin Kochol. Complexity of 3-edge-coloring in cubes with an oriented surface // Discrete Applied Mathematics. - 2010. - Vol. 158 , no. 16 - p . 1856–1860 . - DOI : 10.1016 / j.dam.2010.06.019 .
A constructive proof of Vizing's Theorem // Information Processing Letters . - 1992. - V. 41 , no. 3 - p . 131–133 . - DOI : 10.1016 / 0020-0190 (92) 90041-S .
Daniel P. Sanders, Yue Zhao. Planar graphs of the seven degrees are the class I // Journal of Combinatorial Theory . - 2001. - V. 83 , no. 2 - pp . 201–212 . - DOI : 10.1006 / jctb.2001.2047 .
Claude Shannon. A theorem on the lines of a network // J. Math. Physics. - 1949. - T. 28 . - p . 148-151 .
Alexander Soifer. The Mathematical Coloring Book. - 2008. - pp . 136–137 . - ISBN 978-0-387-74640-1 .
PG Tait. Remarks on the colors of maps // Proc. R. Soc. Edinburgh. - 1880. - Vol . 10 . - p . 729 .
W. G. Vizing. On the estimation of the chromatic class of a p-graph // sat. Discrete analysis. - Novosibirsk: Institute of Mathematics, Siberian Branch of the Academy of Sciences of the USSR, 1964. - Vol . 3 . - p . 25–30 .
W. G. Vizing. Critical graphs with the given chromatic class. Discrete analysis. - Novosibirsk: Institute of Mathematics, Siberian Branch of the USSR Academy of Sciences, 1965. - Vol . 5 . - pp . 9–17 .

Links

Proof of Vizing's Theorem at PlanetMath .

[_9dc6d90cfb7d5c0f-1] Fournier, 1973 .

[_7a7cf5c0fbddfa8d-2] Erdős, Wilson, 1977 .

[_256c16153a592825-3] Frieze, Jackson, McDiarmid, Reed, 1988 .

[_64f40409428227c1-4] ¹ ² Vizing, 1965 .

[_ccaffb162176a01c-5] Sanders, Zhao, 2001 .

[_dab11dc99a1e623c-6] Tait, 1880 .

[_510172eba6742320-7] Kochol, 2009 .

[_983e418733a55ad6-8] Kochol, 2010 .

[_eb68c24404c55bc4-9] Misra, Gries, 1992 .

[10] Алгорит Algorithm description taken from Joachim Breitner article . Proving Vizing's Theorem with Rodin. - 2011.

[_671bffd0c5ebac1e-11] Gabow et al., 1985 .

[_c0fe58193c435645-12] ¹ ² Gutin, Toft, 2000 .

[_031838408401dfa9-13] Soifer, 2008 .

[_778239e52354f01b-14] Shannon, 1949 .

Vizing theorem

Content

Examples

Graph classification

Flat graphs

Counts on surfaces other than planes

Algorithms

History

See also

Notes

Links

Links

More articles: