[2] Indian mathematician R. P. Gupta independently discovered the theorem, while undertaking his doctorate (1965-1967).
We define y0,...,yk to be a maximal sequence of neighbours of x such that c0(xyi) is missing in yi−1 with respect to c0 for all 0 < i ≤ k. We define colorings c1,...,ck as Then ci is a proper (Δ+1)-edge-coloring of G − xyi due to definition of y0,...,yk.
Vizing (1965) showed that a planar graph 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.
The four color theorem (proved by Appel & Haken (1976)) on vertex coloring of planar graphs, is equivalent to the statement that every bridgeless 3-regular planar graph is of class one (Tait 1880).
In 1969, Branko Grünbaum conjectured that every 3-regular graph with a polyhedral embedding on any two-dimensional oriented manifold such as a torus must be of class one.
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 are of class one.
However, Kochol (2009) 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.
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 uv is an uncolored edge in a partially colored graph.
The algorithm of Misra and Gries may be interpreted as constructing a directed pseudoforest P (a graph in which each vertex has at most one outgoing edge) on the neighbors of u: for each neighbor p of u, the algorithm finds a color c that is not used by any of the edges incident to p, finds the vertex q (if it exists) for which edge uq has color c, and adds pq as an edge to P. There are two cases: With some simple data structures to keep track of the colors that are used and available at each vertex, the construction of P and the recoloring steps of the algorithm can all be implemented in time O(n), where n is the number of vertices in the input graph.
In an unpublished technical report, Gabow et al. (1985) claimed a faster