Vizing's theorem

The theorem discovered by Soviet mathematician Vadim G. Vizing was published in 1964 when Vizing was working in Novosibirsk and became known as Vizing's theorem.{{harvtxt|Vizing|1965}} Indian mathematician R. P. Gupta independently discovered the theorem, while undertaking his doctorate (1965-1967).{{cite book|last1=Stiebitz |first1=Michael|last2=Scheide |first2=Diego|last3=Toft|first3=Bjarne|last4=Favrholdt|first4=Lene M.|isbn=978-1-118-09137-1 |mr=2975974|page=xii |publisher=John Wiley & Sons, Inc., Hoboken, NJ|series=Wiley Series in Discrete Mathematics and Optimization|title=Graph Edge Coloring: Vizing's Theorem and Goldberg's Conjecture|url=https://books.google.com/books?id=GAduDt7c0A0C&pg=PR12|year=2012}}{{cite journal |last1=Toft |first1=B |last2=Wilson |first2=R |title=A brief history of edge-colorings – with personal reminiscences |journal=Discrete Mathematics Letters |date=11 March 2021 |volume=6 |pages=38–46 |doi=10.47443/dml.2021.s105|doi-access=free |url=https://findresearcher.sdu.dk/ws/files/181454353/DML21_v6_pp38_46.pdf }}

When {{math|1=Δ = 1}}, the graph {{mvar|G}} must itself be a matching, with no two edges adjacent, and its edge chromatic number is one. That is, all graphs with {{math|1=Δ(G) = 1}} are of class one.

When {{math|1=Δ = 2}}, the graph {{mvar|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 {{math|1=Δ = 2}} is of class one if and only if it is bipartite.

This proof is inspired by {{harvtxt|Diestel|2000}}.

Let {{math|1=G = (V, E)}} be a simple undirected graph. We proceed by induction on {{math|m}}, the number of edges. If the graph is empty, the theorem trivially holds. Let {{math|m > 0}} and suppose a proper {{math|(Δ+1)}}-edge-coloring exists for all {{math|G − xy}} where {{math|xy ∈ E}}.

We say that color {{math|α ∈ {1,...,Δ+1}}} is missing in {{math|x ∈ V}} with respect to proper {{math|(Δ+1)}}-edge-coloring {{math|c}} if {{math|c(xy) ≠ α}} for all {{math|y ∈ N(x)}}. Also, let {{math|α/β}}-path from {{math|x}} denote the unique maximal path starting in {{math|x}} with {{math|α}}-colored edge and alternating the colors of edges (the second edge has color {{math|β}}, the third edge has color {{math|α}} and so on), its length can be {{math|0}}. Note that if {{math|c}} is a proper {{math|(Δ+1)}}-edge-coloring of {{math|G}} then every vertex has a missing color with respect to {{math|c}}.

Suppose that no proper {{math|(Δ+1)}}-edge-coloring of {{math|G}} exists. This is equivalent to this statement:

:(1) Let {{math|xy ∈ E}} and {{math|c}} be arbitrary proper {{math|(Δ+1)}}-edge-coloring of {{math|G − xy}} and {{math|α}} be missing from {{math|x}} and {{math|β}} be missing from {{math|y}} with respect to {{math|c}}. Then the {{math|α/β}}-path from {{math|y}} ends in {{math|x}}.

This is equivalent, because if (1) doesn't hold, then we can interchange the colors {{math|α}} and {{math|β}} on the {{math|α/β}}-path and set the color of {{math|xy}} to be {{math|α}}, thus creating a proper {{math|(Δ+1)}}-edge-coloring of {{math|G}} from {{math|c}}. The other way around, if a proper {{math|(Δ+1)}}-edge-coloring exists, then we can delete {{math|xy}}, restrict the coloring and (1) won't hold either.

Now, let {{math|xy₀ ∈ E}} and {{math|c₀}} be a proper {{math|(Δ+1)}}-edge-coloring of {{math|G − xy₀}} and {{math|α}} be missing in {{math|x}} with respect to {{math|c₀}}. We define {{math|y₀,...,y_k}} to be a maximal sequence of neighbours of {{math|x}} such that {{math|c₀(xy_i)}} is missing in {{math|y_i−1}} with respect to {{math|c₀}} for all {{math|0 < i ≤ k}}.

We define colorings {{math|c₁,...,c_k}} as

:{{math|c_i(xy_j){{=}}c₀(xy_j+1)}} for all {{math|0 ≤ j < i}},

:{{math|c_i(xy_i)}} not defined,

:{{math|c_i(e){{=}}c₀(e)}} otherwise.

Then {{math|c_i}} is a proper {{math|(Δ+1)}}-edge-coloring of {{math|G − xy_i}} due to definition of {{math|y₀,...,y_k}}. Also, note that the missing colors in {{math|x}} are the same with respect to {{math|c_i}} for all {{math|0 ≤ i ≤ k}}.

Let {{math|β}} be the color missing in {{math|y_k}} with respect to {{math|c₀}}, then {{math|β}} is also missing in {{math|y_k}} with respect to {{math|c_i}} for all {{math|0 ≤ i ≤ k}}. Note that {{math|β}} cannot be missing in {{math|x}}, otherwise we could easily extend {{math|c_k}}, therefore an edge with color {{math|β}} is incident to {{math|x}} for all {{math|c_j}}. From the maximality of {{math|k}}, there exists {{math|1 ≤ i < k}} such that {{math|c₀(xy_i) {{=}} β}}. From the definition of {{math|c₁,...,c_k}} this holds:

:{{math|c₀(xy_i) {{=}} c_i−1(xy_i) {{=}} c_k(xy_i−1) {{=}} β}}

Let {{math|P}} be the {{math|α/β}}-path from {{math|y_k}} with respect to {{math|c_k}}. From (1), {{math|P}} has to end in {{math|x}}. But {{math|α}} is missing in {{math|x}}, so it has to end with an edge of color {{math|β}}. Therefore, the last edge of {{math|P}} is {{math|y_i−1x}}. Now, let {{math|P' }} be the {{math|α/β}}-path from {{math|y_i−1}} with respect to {{math|c_i−1}}. Since {{math|P' }} is uniquely determined and the inner edges of {{math|P}} are not changed in {{math|c₀,...,c_k}}, the path {{math|P' }} uses the same edges as {{math|P}} in reverse order and visits {{math|y_k}}. The edge leading to {{math|y_k}} clearly has color {{math|α}}. But {{math|β}} is missing in {{math|y_k}}, so {{math|P' }} ends in {{math|y_k}}. Which is a contradiction with (1) above.

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 {{math|Δ}} in a graph {{mvar|G}} form an independent set, or more generally if the induced subgraph for this set of vertices is a forest, then {{mvar|G}} must be of class one.{{harvtxt|Fournier|1973}}.

{{harvtxt|Erdős|Wilson|1977}} showed that almost all graphs are of class one. That is, in the Erdős–Rényi model of random graphs, in which all {{mvar|n}}-vertex graphs are equally likely, let {{math|p(n)}} be the probability that an {{mvar|n}}-vertex graph drawn from this distribution is of class one; then {{math|p(n)}} approaches one in the limit as {{mvar|n}} goes to infinity. For more precise bounds on the rate at which {{math|p(n)}} converges to one, see {{harvtxt|Frieze|Jackson|McDiarmid|Reed|1988}}.

The general classification problem of graphs into class one or class two was shown in 1981 to be NP-complete.Ian Holyer, "The np-completeness of edge-coloring", SIAM Journal on computing, 10(4):718–720, 1981.

{{harvtxt|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. For degree two, any odd cycle is such a graph, and for degree three, four, and five, these graphs can be constructed from platonic solids by replacing a single edge by a path of two adjacent edges.

In Vizing's planar graph conjecture, {{harvtxt|Vizing|1965}} states that all simple, planar graphs with maximum degree six or seven are of class one, closing the remaining possible cases.

Independently, {{harvtxt|Zhang|2000}} and {{harvtxt|Sanders|Zhao|2001}} 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 (proved by {{harvtxt|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 {{harv|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. In this context, a polyhedral embedding is a graph embedding such that every face of the embedding is topologically a disk and such that the dual graph 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 are of class one. However, {{harvtxt|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.{{harvtxt|Kochol|2010}}.

{{Main|Misra & Gries edge-coloring algorithm}}

As the general classification problem, into either class one or class two, is NP-complete, there is no hope for a polynomial-time algorithm for best edge coloring. However, already Vizing's original proof of his theorem is algorithmic, describing a polynomial-time algorithm for coloring the edges of any graph with {{math|Δ + 1}} colors, where {{math|Δ}} 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: 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. The algorithm thus colors the $m$ edges, with each such recoloring taking $O(n)$ time, for a total time-complexity of $O(m\; n)$.

{{harvtxt|Misra|Gries|1992}} describe an algorithm following the same strategy as Vizing's original one.

More specifically, suppose that {{math|uv}} is an uncolored edge in a partially colored graph. The algorithm of Misra and Gries may be interpreted as constructing a directed pseudoforest {{mvar|P}} (a graph in which each vertex has at most one outgoing edge) on the neighbors of {{mvar|u}}: for each neighbor {{mvar|p}} of {{mvar|u}}, the algorithm finds a color {{mvar|c}} that is not used by any of the edges incident to {{mvar|p}}, finds the vertex {{mvar|q}} (if it exists) for which edge {{mvar|uq}} has color {{mvar|c}}, and adds {{mvar|pq}} as an edge to {{mvar|P}}. There are two cases:

• If the pseudoforest {{mvar|P}} constructed in this way contains a path from {{mvar|v}} to a vertex {{mvar|w}} that has no outgoing edges in {{mvar|P}}, then there is a color {{mvar|c}} that is available both at {{mvar|u}} and {{mvar|w}}. Recoloring edge {{mvar|uw}} with color {{mvar|c}} allows the remaining edge colors to be shifted one step along this path: for each vertex {{mvar|p}} in the path, edge {{mvar|up}} takes the color that was previously used by the successor of {{mvar|p}} in the path. This leads to a new coloring that includes edge {{mvar|uv}}.
• If, on the other hand, the path starting from {{mvar|v}} in the pseudoforest {{mvar|P}} leads to a cycle, let {{mvar|w}} be the neighbor of {{mvar|u}} at which the path joins the cycle, let {{mvar|c}} be the color of edge {{mvar|uw}}, and let {{mvar|d}} be a color that is not used by any of the edges at vertex {{mvar|u}}. Then swapping colors {{mvar|c}} and {{mvar|d}} 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 {{mvar|P}} and the recoloring steps of the algorithm can all be implemented in time {{math|O(n)}}, where {{mvar|n}} is the number of vertices in the input graph. Since these steps need to be repeated {{mvar|m}} times, with each repetition increasing the number of colored edges by one, the total time is {{math|O(mn)}}.

In an unpublished technical report, {{harvtxt|Gabow|Nishizeki|Kariv|Leven|1985}} claimed a faster $O(m\backslash sqrt\; n\backslash log\; n)$ time bound for the same problem of coloring with {{math|Δ + 1}} colors.The same bound also appears in a 1982 paper by Arjomandi{{Cite journal |last=Arjomandi |first=Eshrat |date=May 1982 |title=An Efficient Algorithm for Colouring the Edges of a Graph With Δ + 1 Colours |url=http://www.tandfonline.com/doi/full/10.1080/03155986.1982.11731850 |journal=INFOR: Information Systems and Operational Research |language=en |volume=20 |issue=2 |pages=82–101 |doi=10.1080/03155986.1982.11731850 |issn=0315-5986}}

In 2024, several improved algorithms were developed, culminating with a probabilistic quasilinear time algorithm, having $O(m\; \backslash log\; \backslash Delta)\; =\; \backslash widetilde\{O\}(m)$ time complexity (preprint).{{cite arXiv |last1=Assadi|first1=S.|display-authors =etal|date=2024|title=Vizing’s Theorem in Near-Linear Time|eprint=2410.05240}}{{Cite web |last=Nadis |first=Steve |date=2025-05-12 |title=The Fastest Way Yet to Color Graphs |url=https://www.quantamagazine.org/the-fastest-way-yet-to-color-graphs-20250512/ |access-date=2025-05-17 |website=Quanta Magazine |language=en}}

In both {{harvtxt|Gutin|Toft|2000}} and {{harvtxt|Soifer|2008}}, Vizing mentions that his work was motivated by a theorem of {{harvtxt|Shannon|1949}} showing that multigraphs could be colored with at most {{math|(3/2)Δ}} 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 {{harvtxt|Gutin|Toft|2000}}) and discontinued in 1991 [http://www.ams.org/mathscinet/search/journaldoc.html?jc=DISKA].

• Brooks' theorem relating vertex colorings to maximum degree

{{reflist}}

• {{citation

| last1 = Appel | first1 = K. | author1-link = Kenneth Appel

| last2 = Haken | first2 = W. | author2-link = Wolfgang Haken

| doi = 10.1090/S0002-9904-1976-14122-5

| issue = 5

| journal = Bulletin of the American Mathematical Society

| mr = 0424602

| pages = 711–712

| title = Every planar map is four colorable

| volume = 82

| year = 1976| doi-access = free

}}.

• {{Citation | last1=Diestel | first1=Reinhard | title=Graph Theory | pages=103–104| url=https://www.emis.de/monographs/Diestel/en/GraphTheoryII.pdf | publisher=Springer-Verlag | location=Berlin, New York | year=2000 }}.
• {{citation

| last1 = Erdős | first1 = Paul | authorlink1 = Paul Erdős

| last2 = Wilson | first2 = Robin J. | authorlink2 = Robin Wilson (mathematician)

| year = 1977

| title = Note on the chromatic index of almost all graphs

| journal = Journal of Combinatorial Theory | series = Series B

| volume = 23

| pages = 255–257

| url = http://www.renyi.hu/~p_erdos/1977-20.pdf

| doi = 10.1016/0095-8956(77)90039-9

| issue = 2–3| doi-access = free

}}.

• {{citation

| last = Fournier | first = Jean-Claude

| journal = Cahiers du Centre d'Études de Recherche Opérationnelle

| mr = 0349458

| pages = 311–314

| title = Colorations des arêtes d'un graphe

| volume = 15

| year = 1973}}.

• {{citation

| last1 = Frieze | first1 = Alan M. | author1-link = Alan M. Frieze

| last2 = Jackson | first2 = B.

| last3 = McDiarmid | first3 = C. J. H.

| last4 = Reed | first4 = B. | author4-link = Bruce Reed (mathematician)

| doi = 10.1016/0095-8956(88)90065-2

| issue = 2

| journal = Journal of Combinatorial Theory | series = Series B

| mr = 961145

| pages = 135–149

| title = Edge-colouring random graphs

| volume = 45

| year = 1988| doi-access =

}}.

• {{citation

| last1 = Gabow | first1 = Harold N. | author1-link = Harold N. Gabow

| last2 = Nishizeki | first2 = Takao | author2-link = Takao Nishizeki

| last3 = Kariv | first3 = Oded

| last4 = Leven | first4 = Daniel

| last5 = Terada | first5 = Osamu

| publisher = Tohoku University

| series = Tech. Report TRECIS-8501

| title = Algorithms for edge-coloring graphs

| year = 1985}}.

• {{citation|first1=Gregory|last1=Gutin|first2=Bjarne|last2=Toft|title=Interview with Vadim G. Vizing|journal=European Mathematical Society Newsletter|volume=38|date=December 2000|pages=22–23|url=http://www.emis.de/newsletter/newsletter38.pdf}}.
• {{citation

| last = Kochol | first = Martin

| contribution = Polyhedral embeddings of snarks in orientable surfaces

| pages = 1613–1619

| volume = 137

| title = Proceedings of the American Mathematical Society

| year = 2009}}.

• {{citation

| last = Kochol | first = Martin

| doi = 10.1016/j.dam.2010.06.019

| issue = 16

| journal = Discrete Applied Mathematics

| mr = 2679785

| pages = 1856–1860

| title = Complexity of 3-edge-coloring in the class of cubic graphs with a polyhedral embedding in an orientable surface

| volume = 158

| year = 2010| doi-access = free

}}.

• {{citation

| last1 = Misra | first1 = J.

| last2 = Gries | first2 = David | author2-link = David Gries

| doi = 10.1016/0020-0190(92)90041-S

| issue = 3

| journal = Information Processing Letters

| pages = 131–133

| title = A constructive proof of Vizing's Theorem

| volume = 41

| year = 1992}}.

• {{citation

| authorlink = Daniel P. Sanders | last1 = Sanders | first1 = Daniel P. | last2 = Zhao | first2 = Yue | year = 2001

| title = Planar graphs of maximum degree seven are class I

| journal = Journal of Combinatorial Theory, Series B | volume = 83 | issue = 2 | pages = 201–212

| doi = 10.1006/jctb.2001.2047| doi-access = free }}.

• {{citation

| last = Shannon | first = Claude E. | authorlink = Claude Shannon

| title = A theorem on coloring the lines of a network | mr = 0030203

| journal = J. Math. Physics | volume = 28 | year = 1949 | issue = 1–4 | pages = 148–151| doi = 10.1002/sapm1949281148 }}.

• {{citation|first=Alexander|last=Soifer|year=2008|title=The Mathematical Coloring Book|title-link=The Mathematical Coloring Book|publisher=Springer-Verlag|isbn=978-0-387-74640-1|pages=136–137}}.
• {{Citation | authorlink=Peter Guthrie Tait|first=P. G.|last= Tait| title=Remarks on the colourings of maps| journal=Proc. R. Soc. Edinburgh| volume=10| year=1880| pages=729|doi=10.1017/S0370164600044643 }}.
• {{citation

| last = Vizing | first = V. G. | year = 1964 | authorlink = Vadim G. Vizing

| title = On an estimate of the chromatic class of a p-graph | mr = 0180505

| journal = Diskret. Analiz. | volume = 3 | pages = 25–30}}.

• {{citation

| last = Vizing | first = V. G. | year = 1965 | authorlink = Vadim G. Vizing

| title = Critical graphs with given chromatic class

| journal = Metody Diskret. Analiz. | volume = 5 | pages = 9–17}}. (In Russian.)

• {{citation

| last1 = Zhang | first1 = Limin| year = 2000

| title = Every planar graph with maximum degree 7 is of class 1

| journal = Graphs and Combinatorics | volume = 16 | issue = 4 | pages = 467–495| doi = 10.1007/s003730070009| s2cid = 10945647}}.

• [http://planetmath.org/?op=getobj&from=objects&id=6932 Proof of Vizing's theorem] at PlanetMath.

Category:Graph coloring

Category:Theorems in graph theory