Are you an EPFL student looking for a semester project?
Work with us on data science and visualisation projects, and deploy your project as an app on top of Graph Search.
Concept
Vizing's theorem
Summary
In graph theory, Vizing's theorem states that every simple undirected graph may be edge colored using a number of colors that is at most one larger than the maximum degree Δ 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 Δ + 1 colors are necessary. A more general version of Vizing's theorem states that every undirected multigraph without loops can be colored with at most Δ+μ colors, where μ is the multiplicity of the multigraph. The theorem is named for Vadim G. Vizing who published it in 1964.
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. Indian mathematician R. P. Gupta independently discovered the theorem, while undertaking his doctorate (1965-1967).
When Δ = 1, the graph G must itself be a matching, with no two edges adjacent, and its edge chromatic number is one. That is, all graphs with Δ(G) = 1 are of class one.
When Δ = 2, the graph G must be a disjoint union 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 Δ = 2 is of class one if and only if it is bipartite.
This proof is inspired by .
Let G = (V, E) be a simple undirected graph. We proceed by induction on m, the number of edges. If the graph is empty, the theorem trivially holds. Let m > 0 and suppose a proper (Δ+1)-edge-coloring exists for all G − xy where xy ∈ E.
We say that color α ∈ {1,...,Δ+1} is missing in x ∈ V with respect to proper (Δ+1)-edge-coloring c if c(xy) ≠ α for all y ∈ N(x). Also, let α/β-path from x denote the unique maximal path starting in x 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 0.
Official source
About this result
This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.