Übersetzung für 'Vizing\'s' von Englisch nach Deutsch

Vizing's theorem [also: Vizing theorem, theorem of Vizing]

Satz {m} von Vizingmath.

• The theorem discovered by Russian mathematician Vadim G. Vizing was published in 1964 when Vizing was working in Novosibirsk and became known as Vizing's theorem.
• In 2019, an alleged proof was announced by Chen, Jing, and Zang in the paper. Part of their proof was to find a suitable generalization of Vizing's theorem (which says that for simple graphs [...]) to multigraphs.
• Total coloring arises naturally since it is simply a mixture of vertex and edge colorings. The next step is to look for any Brooks-typed or Vizing-typed upper bound on the total chromatic number in terms of maximum degree.
• Vizing's theorem can be interpreted as stating that the line graphs are [...] -bounded, with [...]. [...] The claw-free graphs more generally are also [...] -bounded with [...]. This can be seen by using Ramsey's theorem to show that, in these graphs, a vertex with many neighbors must be part of a large clique.
• In addition to vertex coloring, other types of coloring are also studied, such as edge colorings. The chromatic index [...] of a graph [...] is the minimum number of colors in a proper edge-coloring of a graph, and Vizing's theorem states that the chromatic index of a graph [...] is either [...] or [...].

• A version of Vizing's theorem [...] states that every multigraph with maximum degree [...] and multiplicity [...] may be colored using at most [...] colors. Again, this bound is tight for the Shannon multigraphs.
• Vadim Georgievich Vizing ([...] , [...]; 25 March 1937 – 23 August 2017) [...] was a Soviet and Ukrainian mathematician known for his contributions to graph theory, and especially for Vizing's theorem stating that the edges of any simple graph with maximum degree Δ can be colored with at most Δ + 1 colors.
• The Misra & Gries edge coloring algorithm is a polynomial time algorithm in graph theory that finds an edge coloring of any graph. The coloring produced uses at most [...] colors, where [...] is the maximum degree of the graph. This is optimal for some graphs, and by Vizing's theorem it uses at most one color more than the optimal for all others.