Fact-checked by Grok 2 weeks ago

Vizing's theorem

Vizing's theorem is a foundational result in graph theory stating that for every simple finite undirected graph G, the edge chromatic number \chi'(G) satisfies \Delta(G) \leq \chi'(G) \leq \Delta(G) + 1, where \Delta(G) denotes the maximum degree of G.^[1] The lower bound follows directly from the fact that the \Delta(G) edges incident to a maximum-degree vertex must receive distinct colors in any proper edge coloring.^[1] This theorem classifies all simple graphs into two mutually exclusive categories: Class 1 graphs, for which \chi'(G) = \Delta(G), and Class 2 graphs, for which \chi'(G) = \Delta(G) + 1.^[2] The theorem was established by the Soviet mathematician Vadim G. Vizing in 1964, as detailed in his seminal paper "On an Estimate of the Chromatic Class of a p-Graph," published in Diskretnyĭ Analiz.^[1] Vizing's original proof is non-constructive, relying on the existence of certain fan structures in partially colored graphs to extend colorings, but it provides tight bounds that have profoundly influenced the study of edge colorings.^[1] A polynomial-time constructive proof was later developed by Jay Misra and David Gries in 1992, offering an explicit algorithm to edge-color any simple graph with at most \Delta + 1 colors by iteratively coloring edges and resolving conflicts via color shifts and inversions.^[3] Vizing's theorem serves as the cornerstone of edge-chromatic graph theory, enabling the analysis of scheduling problems, resource allocation, and network design where edges represent constraints requiring distinct labels. It generalizes Brooks' theorem from vertex to edge colorings and underpins open conjectures, such as Vizing's planar graph conjecture, which posits that every planar graph with \Delta \geq 6 is Class 1.^[4] Determining whether a given graph is Class 1 or Class 2 is NP-complete, highlighting the theorem's computational challenges despite its sharp theoretical bounds.^[5] Recent algorithmic advances, including a randomized near-linear time procedure for edge-coloring graphs with maximum degree \Delta using \Delta + 1 colors (as of 2024), have further practicalized the theorem's implications.^[6]

Statement and Fundamentals

Theorem Statement

Vizing's theorem is a fundamental result in graph theory concerning the edge chromatic number of simple graphs. The chromatic index \chi'(G) of a graph G is defined as the minimum number of colors required to color the edges of G such that no two adjacent edges (i.e., edges sharing a common vertex) receive the same color.^[7] The theorem states that for every simple finite undirected graph G, the chromatic index satisfies \Delta(G) \leq \chi'(G) \leq \Delta(G) + 1, where \Delta(G) denotes the maximum degree of G.^[7] This result, proved by Vadim G. Vizing in 1964, classifies simple graphs into two types based on whether \chi'(G) = \Delta(G) (class one graphs) or \chi'(G) = \Delta(G) + 1 (class two graphs), though it does not determine the class for a given graph.^[7] As an immediate consequence, every simple graph admits an edge coloring using at most \Delta(G) + 1 colors, providing a tight upper bound on the edge chromatic number relative to the lower bound given by \Delta(G).^[7] The theorem highlights the narrow range of possible values for \chi'(G) but leaves open the challenging problem of distinguishing between the two classes.^[7]

Edge Coloring Concepts

In graph theory, an edge coloring of a graph G = (V, E) is a function C: E \to S, where S is a set of colors, such that no two edges incident to the same vertex receive the same color.^[2] This ensures that adjacent edges—those sharing a common vertex—are distinguished by their colors, providing a way to partition the edges into matchings, where each matching consists of edges that do not share vertices.^[8] The chromatic index of a graph G, denoted \chi'(G), is the minimum number of colors required to achieve a proper edge coloring of G.^[9] This value represents the edge-chromatic number and is a fundamental measure of the graph's edge-coloring complexity, directly related to the size of the largest matching needed to cover all edges without conflicts at vertices.^[2] The maximum degree of a graph G, denoted \Delta(G), is the largest number of edges incident to any single vertex in G.^[10] It serves as a lower bound for \chi'(G), since at least \Delta(G) colors are necessary to color the edges around a vertex of maximum degree without repetition.^[2] Edge coloring is closely tied to vertex coloring through the line graph L(G) of G, where the vertices of L(G) correspond to the edges of G, and two vertices in L(G) are adjacent if the corresponding edges in G share a vertex.^[11] Consequently, \chi'(G) = \chi(L(G)), where \chi(L(G)) is the chromatic number of the line graph, meaning the minimum colors needed to color the vertices of L(G) such that adjacent vertices differ in color.^[12] Vizing's theorem addresses a key question on bounding the chromatic index, establishing that for any simple graph G, \chi'(G) is either \Delta(G) or \Delta(G) + 1.^[1] This result, posed and resolved by Vizing in 1964, provides a tight upper bound and classifies graphs based on whether they achieve the lower or higher value.^[1]

Historical Development

Discovery and Attribution

Vizing's theorem is named after the Soviet mathematician Vadim G. Vizing, who established the result in 1964 while working as a graduate student in Novosibirsk. Born in 1937 in what is now Ukraine, Vizing was a leading figure in graph theory, with a career focused on edge and vertex coloring problems; he studied at the University of Tomsk and earned his Ph.D. in 1966 in Novosibirsk before moving to Ukraine in 1968, where he taught mathematics until retirement. Vizing died on September 5, 2017, in Odessa, Ukraine.^[13] The theorem first appeared in Vizing's paper titled "On an estimate of the chromatic class of a p-graph" (in Russian), published in the journal Diskret. Analiz, volume 3, pages 25–30. In this work, Vizing introduced the classification of simple graphs into chromatic classes based on their edge chromatic numbers relative to the maximum degree. This result built on foundational work in edge coloring, particularly Dénes Kőnig's 1931 theorem, which proved that bipartite graphs can be edge-colored with exactly Δ colors, where Δ is the maximum degree.^[14] Prior to Vizing, mathematicians had sought to extend this equality to non-bipartite graphs, but no tight bound existed; Vizing's theorem provided the key generalization, bounding the edge chromatic number between Δ and Δ + 1 for any simple graph.

Subsequent Advances

Following Vizing's original work, significant progress has been made on his conjecture that every planar graph with maximum degree \Delta \geq 6 is of class 1, meaning its edge chromatic number \chi'(G) = \Delta. Vizing himself proved the conjecture for \Delta \geq 8 in 1965. The case \Delta = 7 was resolved affirmatively in 2000 by Zhang and in 2001 independently by Sanders and Zhao, establishing that all planar graphs with \Delta = 7 are class 1. However, the case \Delta = 6 remains open as of 2025. Vizing extended his theorem to multigraphs in 1965, classifying the edge chromatic number \chi'(G) for any multigraph G with maximum degree \Delta and maximum edge multiplicity \mu as lying between \Delta and \Delta + \mu. This bound refines the simple graph case, where \mu = 1, and has been foundational for studying edge colorings in graphs allowing multiple edges. A key related result is Holyer's theorem from 1981, which demonstrates that determining whether the edge chromatic number of a cubic graph (where \Delta = 3) is 3 or 4 is NP-complete. This highlights the computational difficulty of classifying graphs as class 1 or class 2, even in restricted cases. Recent advances include partial progress on the overfull conjecture, which posits that a class 2 graph contains an overfull subgraph (one with more than \Delta \cdot |V(H)| / 2 edges) of the same maximum degree; a 2023 result provides the first breakthrough without assuming a minimum degree condition.^[15] For snarks—cyclically 4-edge-connected cubic class 2 graphs—ongoing work in the 2020s has yielded partial classifications and structural insights, often linking them to overfull subgraphs. Additionally, algorithmic developments in the 2020s have enabled computation of (\Delta + 1)-edge colorings in near-linear time for general graphs.^[6]

Proof Techniques

Core Proof Strategy

Vizing's theorem asserts that the chromatic index of any simple graph G with maximum degree \Delta satisfies \chi'(G) \leq \Delta + 1, implying that G is either class 1 (\chi'(G) = \Delta) or class 2 (\chi'(G) = \Delta + 1). The proof demonstrates the upper bound constructively by building a valid (\Delta + 1)-edge coloring through iterative adjustments, ensuring no two adjacent edges share the same color. This approach avoids exhaustive enumeration by focusing on resolving local color deficiencies at high-degree vertices, leveraging the graph's structure to extend partial colorings without increasing the color set beyond \Delta + 1.^[16] The core strategy employs induction on the size of the graph, typically measured by the number of edges or vertices. For the inductive base, graphs with no edges or isolated vertices are trivially colorable with 0 or 1 colors, well within the bound. Assuming the result holds for all smaller graphs, consider a graph G with maximum degree \Delta \geq 1. Select a vertex v of degree \Delta and apply the inductive hypothesis to G - v, yielding a (\Delta + 1)-edge coloring of the subgraph. The challenge lies in extending this coloring to the edges incident to v, which may introduce conflicts due to colors already used by neighbors of v. To address this, the proof iteratively fixes deficiencies—situations where an incident edge at v cannot be assigned an available color—by recoloring substructures around v while preserving the validity elsewhere.^[17] Central to the extension is the fan argument, a local reconfiguration tool centered at v. A fan at v is constructed as a sequence of edges incident to v, ordered by their colors and connected through alternating paths in the subgraph induced by two specific colors. If a conflict arises (e.g., two consecutive fan edges share a problematic color pair), a rotation of the fan shifts the colors along this path, freeing a color for the deficient edge. This process is repeated until no deficiencies remain, ensuring all \Delta edges at v are properly colored using at most \Delta + 1 colors. The fan's maximality guarantees progress, as any unresolved conflict would imply a smaller recolorable structure, contradicting the inductive assumption.^[16] Complementing the fan rotations is the Kempe chain method, which resolves deeper conflicts by identifying alternating paths (Kempe chains) in bichromatic subgraphs. Starting from a vertex with a missing color pair \{\alpha, \beta\}, the chain traces edges alternating between \alpha and \beta until it terminates at another high-degree vertex. Swapping colors along this chain (a Kempe swap) alters the availability of colors at the endpoints without affecting the rest of the coloring. If multiple chains intersect or terminate appropriately, combined swaps free the necessary color for the deficient edge. This technique ensures that the recoloring remains local and bounded, preventing the need for more than \Delta + 1 colors overall. The interplay of fans and Kempe chains provides a systematic way to propagate color adjustments, confirming the bound for G.^[17]

Supporting Lemmas

Critical graphs play a central role in the inductive proof of Vizing's theorem by allowing reduction to irreducible cases where the edge-chromatic number exceeds the maximum degree. A graph G is defined as \Delta + 1-edge-chromatic critical if \chi'(G) = \Delta(G) + 1 and for every edge e \in E(G), \chi'(G - e) \leq \Delta(G). These graphs are minimal with respect to having chromatic index \Delta + 1, enabling the analysis of structural properties that facilitate coloring extensions. In the proof, any graph with \chi' > \Delta contains a critical subgraph, and coloring proceeds by induction on the number of edges, assuming proper partial colorings and resolving conflicts in these critical structures.^[18] The fan lemma provides a key tool for recoloring around a high-degree vertex in a partial edge coloring. Consider a partial proper (\Delta + 1)-edge-coloring of a simple graph G with maximum degree \Delta, and let xy be an uncolored edge incident to a \Delta-vertex x. A \phi-shiftable fan F centered at x with starting edge xy is a sequence of distinct neighbors of x such that consecutive edges in the fan satisfy specific color availability conditions: the color on one edge is missing at the next vertex, allowing a shift without conflicts. The lemma states that such a fan exists that is either \phi-happy (all colors at x are used except one missing at y) or (\phi, \alpha \beta)-successful for distinct colors \alpha, \beta \in [\Delta + 1], meaning an alternating \alpha \beta-path from x to y can be inverted to color xy. This structure ensures a color can be freed at x by minimal recoloring.^[19] Path augmentation techniques extend partial colorings by leveraging alternating paths to resolve missing colors at vertices. In a partial coloring \phi, for colors c and d missing at a vertex x but present elsewhere, a cd-path is a maximal alternating path starting at x with edges colored only c or d. Inverting this path—switching c to d and vice versa along the path—frees color d at x while preserving the proper coloring, as the path endpoints have the appropriate missing colors. This operation is crucial for augmenting the coloring when a fan alone does not suffice, particularly in resolving conflicts at the other endpoint y of an uncolored edge. If the path terminates at a vertex where one color is missing, it directly enables coloring the target edge.^[3] Vizing's fan rotation is a specific recoloring operation that shifts colors along a fan to free a desired color without introducing new conflicts. Given a fan F = \langle f_1, \dots, f_k \rangle centered at vertex X with uncolored edge X f_1, and a color d missing at X but available at some f_w, the rotation assigns to each edge X f_i (for i = 1 to k-1) the color previously on X f_{i+1}, and uncolors X f_k. This cyclic shift ensures that the colors remain distinct at X and at each f_i, as the fan's construction guarantees the shifted color is missing at f_i. The operation increases the number of colored edges incident to X by one, allowing X f_w to be colored with d. Repeated rotations along extended fans resolve coloring deficiencies in partial colorings.^[3]

Illustrative Examples

Simple Graph Cases

Vizing's theorem asserts that the chromatic index \chi'(G) of a simple graph G is either \Delta(G) or \Delta(G) + 1, where \Delta(G) is the maximum degree.^[2] Simple graph cases provide clear illustrations of both class 1 graphs, where \chi'(G) = \Delta(G), and class 2 graphs, where \chi'(G) = \Delta(G) + 1. For complete graphs K_n, the maximum degree is \Delta = n-1. When n is even, K_n is class 1 and admits an edge coloring with n-1 colors, as the edges can be decomposed into n-1 perfect matchings. When n is odd, K_n is class 2, requiring n colors, since each color class can cover at most n-1 edges incident to a vertex, leaving one edge per vertex uncolored in any (n-1)-coloring.^[20] Cycle graphs C_n have maximum degree \Delta = 2. For even n, C_n is class 1 and 2-edge-colorable by alternating two colors around the cycle. For odd n, C_n is class 2, necessitating 3 colors, as an odd-length cycle cannot be properly 2-edge-colored without adjacent edges sharing a color at the closing vertex.^[21] Bipartite graphs, including all forests and trees, are always class 1 by König's theorem, which guarantees an edge coloring with \Delta colors, matching the theorem's lower bound.^[22] Trees, as acyclic bipartite graphs, inherit this property and are \Delta-edge-colorable; for instance, a star graph with \Delta leaves requires exactly \Delta colors at the central vertex.^[2]

Overfull and Snarks

A graph G is overfull if the number of edges satisfies |E(G)| > [\Delta(G)](/page/Delta) \lfloor |V(G)|/2 \rfloor, where \Delta(G) is the maximum degree.^[23] By the pigeonhole principle, in any proper edge coloring with \Delta(G) colors, the maximum number of edges that can be colored is at most \Delta(G) \lfloor |V(G)|/2 \rfloor, so every overfull graph requires \Delta(G) + 1 colors and thus belongs to Vizing's class 2.^[23] A classic example is the complete graph K_{2n+1} of odd order, which has \Delta = 2n, |V| = 2n+1, and |E| = n(2n+1) > 2n^2 = \Delta \lfloor |V|/2 \rfloor.^[24] Snarks provide another family of class 2 graphs, specifically those that are cubic (3-regular), bridgeless, and non-3-edge-colorable.^[25] The Petersen graph, discovered by Julius Petersen in 1898, is the smallest snark with 10 vertices and serves as the foundational example of a cubic class 2 graph.^[26] It is non-Hamiltonian and requires 4 colors for edge coloring despite \Delta = 3. The Blanuša snarks, constructed by Danilo Blanuša in 1946, are the next known examples on 18 vertices; they are also non-Hamiltonian cubic bridgeless graphs with chromatic index 4.^[26] These constructions highlight persistent challenges in edge coloring cubic graphs, as conjectures like the four color theorem for planar graphs relate to avoiding snarks.^[27] One method to construct class 2 graphs involves modifying class 1 graphs by incorporating structures akin to odd blossoms, such as in the flower snarks J_t for odd t \geq 5. These graphs are built by attaching odd-length cycles (petals) to a central cycle with spokes, resulting in a cubic bridgeless graph that is class 2.^[27] For instance, the flower snark J_5 on 20 vertices requires 4 colors, demonstrating how adding such odd cyclic attachments forces the chromatic index to \Delta + 1. This approach illustrates systematic ways to generate infinite families of class 2 graphs from simpler colorable bases. Overfull graphs and snarks demonstrate the sharpness of Vizing's bound, as they achieve \chi'(G) = \Delta(G) + 1 while satisfying the theorem's conditions, confirming that the upper bound cannot be tightened universally.^[26] Their existence underscores the theorem's precision, influencing research into conjectures like the overfull conjecture, which posits conditions under which graphs are class 2 due to overfull subgraphs.^[28] These examples also motivate studies in computational complexity and structural graph theory, revealing the diversity of graphs attaining the bound's maximum.

Graph Classifications

Class 1 Graphs

Class 1 graphs are simple undirected graphs whose edges can be properly colored using exactly Δ colors, where Δ denotes the maximum degree of the graph.^[29] This means the chromatic index χ'(G) equals Δ(G), achieving the theoretical lower bound established by Vizing's theorem.^[2] A prominent sufficient condition for a graph to be Class 1 is bipartiteness. By König's theorem, every bipartite graph has chromatic index equal to its maximum degree, as its edges can be decomposed into Δ perfect matchings in the bipartite case.^[22] For example, the complete bipartite graph K_{m,n} (with Δ = max(m,n)) is Class 1 and admits an explicit edge coloring via a systematic assignment of colors to the edges connecting the partite sets.^[29] Another family of Class 1 graphs consists of complete graphs of even order. The complete graph K_{2m} has Δ = 2m - 1 and can be edge-colored with exactly 2m - 1 colors through a 1-factorization into 2m - 1 perfect matchings, such as by arranging vertices in a regular polygon and rotating matchings.^[2] Similarly, even cycles (which are bipartite) are Class 1 with χ' = 2 = Δ.^[29] There is no known simple structural characterization of Class 1 graphs, and deciding whether a given graph is Class 1 or Class 2 is NP-complete.^[29] For regular graphs of degree Δ, being Class 1 is equivalent to admitting a 1-factorization, a decomposition of the edge set into Δ perfect matchings (1-factors).^[2] This connection highlights the role of decomposability in identifying such graphs, though broader characterizations remain elusive despite extensive study.^[29]

Class 2 Graphs

Class 2 graphs are simple graphs G whose chromatic index satisfies \chi'(G) = \Delta(G) + 1, where \Delta(G) denotes the maximum degree of G.^[2] By Vizing's theorem, these are the graphs that require one more color than the minimum possible bound for proper edge coloring.^[30] Such graphs arise when the structure prevents a \Delta(G)-edge-coloring, often due to parity or density issues in the edge set. A sufficient condition for a graph to be class 2 is the presence of an overfull subgraph H, defined as a subgraph where |E(H)| > \Delta(G) \cdot \lfloor |V(H)| / 2 \rfloor. In this case, any \Delta(G)-edge-coloring of G would require at most \lfloor |V(H)| / 2 \rfloor edges per color class in H, implying \chi'(H) > \Delta(G) and thus \chi'(G) = \Delta(G) + 1.^[31] Another necessary condition appears in regular graphs: any k-regular graph on an odd number of vertices is class 2, as the total edges kn/2 cannot be evenly partitioned into k matchings when n is odd.^[2] Odd-order complete graphs K_n (with n odd) exemplify this, being (n-1)-regular on an odd vertex set and hence requiring n colors for edge coloring.^[2] Known families of class 2 graphs include odd cycles, which have \Delta = 2 but require 3 colors since they cannot be decomposed into 2 perfect matchings.^[32] Snarks form another prominent family: these are bridgeless 3-regular graphs that are class 2, with the Petersen graph as the smallest example.^[2] While certain multigraphs can also be class 2, the focus in simple graphs highlights these structures where edge density or cyclomatic properties force the extra color. For instance, the Petersen graph, a snark, illustrates a non-overfull class 2 graph.^[2] Determining whether a general graph is class 1 or class 2 is NP-complete, even when restricted to cubic graphs where the question reduces to 3-edge-colorability.^[30] This complexity underscores the challenge in classifying graphs under Vizing's dichotomy.

Special Graph Families

Planar Graphs

Vizing's planar graph conjecture asserts that every simple planar graph with maximum degree \Delta \geq 6 has edge chromatic number \chi'(G) = \Delta, classifying it as class 1.^[33] This conjecture refines Vizing's theorem for planar graphs, predicting that the upper bound \Delta + 1 is unnecessary when \Delta \geq 6. The result holds for \Delta \geq 8, as originally established by Vizing, who showed that such graphs admit a \Delta-edge-coloring.^[34] For \Delta = 7, the conjecture was confirmed by Zhang, proving that every planar graph with maximum degree 7 is class 1.^[35] The case \Delta = 6 remains unresolved, representing the sole open instance of the conjecture. Significant progress includes Zhang's 2007 theorem, which demonstrates that every simple planar graph with \Delta = 6 lacking a chorded 5-cycle is class 1.^[36] Additional structural restrictions, such as the absence of certain short cycles or specific configurations, have also been shown to guarantee class 1 status for \Delta = 6.^[37] No counterexamples have emerged as of 2025, and exhaustive checks on small planar graphs with \Delta = 6 consistently support the conjecture.^[38] For planar graphs with \Delta \leq 5, outcomes vary by structure, with both class 1 and class 2 examples existing. The complete graph K_4 provides a basic class 1 instance with \Delta = 3, admitting a 3-edge-coloring.^[2] However, class 2 planar graphs arise for \Delta = 3, 4, 5; Vizing constructed them by subdividing a single edge in K_4, the octahedron, and the icosahedron, respectively, yielding graphs requiring \Delta + 1 colors. The conjecture intersects with the four color theorem through Tait colorings: a proper 3-edge-coloring of a bridgeless cubic planar graph corresponds to a proper 4-vertex-coloring of its line graph, establishing that such graphs are class 1 for \Delta = 3.^[2] This equivalence underscores the foundational role of edge coloring in planar graph theory.

Nonplanar Surfaces

Vizing's theorem extends directly to simple graphs embeddable on any fixed surface, asserting that the edge chromatic number χ' satisfies Δ ≤ χ' ≤ Δ + 1, where Δ is the maximum degree. However, for graphs embeddable on a nonplanar surface of genus g ≥ 1, tighter upper bounds on χ' have been established that depend on both g and Δ, often showing χ' = Δ for sufficiently large Δ. These refinements arise from structural properties of embeddings on surfaces with positive genus, where the maximum degree of class 2 graphs (those with χ' = Δ + 1) is bounded by a function of the Euler characteristic χ(Σ) = 2 - 2g of the surface. In particular, the quantity Δ(Σ), defined as the supremum of Δ over all class 2 simple graphs embeddable on Σ, is finite for each fixed surface and grows with the genus, implying χ' ≤ Δ + f(g, Δ) where f(g, Δ) = 0 when Δ exceeds Δ(Σ).^[39] For toroidal graphs, embeddable on the torus (orientable genus g = 1, χ(Σ) = 0), the bound is particularly strong: simple toroidal graphs with Δ ≥ 8 are class 1, so χ' = Δ. This result, obtained via discharging methods, improves Vizing's general bound and confirms that class 2 toroidal graphs have Δ ≤ 7. Examples of class 2 toroidal graphs achieving Δ = 6 or 7 include certain overfull subgraphs, but no simple class 2 toroidal graphs exist beyond this threshold.^[40]^[39] On higher-genus orientable surfaces (g ≥ 2, χ(Σ) ≤ -2), analogous results hold, with χ' = Δ for graphs satisfying degree conditions relative to the surface's topology. For instance, on surfaces with χ(Σ) ≤ -8, simple graphs with minimum degree δ ≥ 7 and Δ ≥ H(χ(Σ)) (the Heawood number, the maximum chromatic number for vertex colorings on the surface) are class 1. These findings, building on earlier work by researchers such as Mel'nikov and extended through structural graph theory, demonstrate that as the genus increases, the threshold for class 1 behavior occurs at larger Δ, but Vizing's Δ + 1 bound remains valid while being asymptotically sharp only up to Δ(Σ). For χ(Σ) ∈ {-7, -6}, Δ(Σ) = 10, and for specific ranges like χ(Σ) ∈ {-22, -21, ..., -8}, Δ(Σ) ≤ H(χ(Σ)).^[39]^[40] Adaptations of the overfull conjecture to nonplanar surfaces highlight the role of overfull subgraphs in classifying class 2 graphs. An overfull graph H satisfies |E(H)| > Δ(H) ⋅ ⌊|V(H)|/2⌋, implying χ'(H) ≥ Δ(H) + 1 by the pigeonhole principle, regardless of embeddability. On nonplanar surfaces, overfull complete graphs K_{2k+1} (which are class 2 and overfull) can be embedded when their genus ceiling((k-1)(k-2)/3) ≤ g; for example, K_7 (Δ = 6) embeds on the torus and exemplifies a class 2 overfull toroidal graph. Such constructions inform adaptations of the conjecture, suggesting that class 2 graphs on surfaces of genus g often contain overfull subgraphs embeddable on the same surface, though counterexamples to the full conjecture exist in higher genus.^[39]

Computational Aspects

Edge Coloring Algorithms

Vizing's algorithm provides a constructive proof of the theorem by iteratively extending a partial edge coloring to the entire graph using a greedy fan-based approach. The method begins with an arbitrary partial coloring and selects an uncolored edge incident to a vertex of maximum degree \Delta. It then constructs a "fan" at that vertex—a sequence of edges alternating between colored and uncolored, or using missing colors—and rotates colors along the fan to free up a color for the uncolored edge without creating conflicts. This process repeats until all edges are colored, guaranteeing a proper (\Delta + 1)-edge coloring. Earlier implementations run in O(|E|^2) time due to the quadratic cost of searching for fans and rotations in the worst case, but a modern randomized version achieves this in O(m \log n) time with high probability, where m = |E| and n = |V|.[^[41]] More efficient polynomial-time algorithms for (\Delta + 1)-edge coloring build on similar ideas but implement them via repeated matching augmentations in auxiliary graphs. These approaches model the coloring problem as finding augmenting paths or cycles in a graph where vertices represent colors at endpoints, allowing the extension of partial colorings by resolving conflicts through maximum matching computations. For instance, Gabow et al. developed an algorithm that colors simple graphs in O(|V| |E| \log |V|) time by integrating efficient matching algorithms with Vizing's fan rotations, making it practical for moderate-sized graphs. Such methods ensure the bound is achieved without exceeding polynomial time, though they may involve more complex data structures for tracking color availabilities. Recent advances, including the aforementioned near-linear time algorithm, further improve efficiency for large graphs.[^[42]] For attempting a \Delta-edge coloring, particularly in graphs suspected to be Class 1, a common heuristic is to iteratively decompose the graph into matchings, aiming for a 1-factorization when the graph is \Delta-regular. This involves greedily assigning edges to color classes by finding maximum matchings in the remaining uncolored subgraph, using algorithms like Hopcroft-Karp for bipartite subproblems or general matching heuristics. If the graph is Class 2, this may fail and require an extra color, but it often succeeds for many practical instances like bipartite or planar graphs. The heuristic runs in polynomial time per iteration but may need backtracking for optimality.[^[43]] Practical software implementations of these algorithms facilitate computation in research and applications. For example, the Python library NetworkX provides tools for graph manipulation that support user-implemented edge coloring via Vizing-like greedy methods or matching-based approaches, often integrated with its coloring module for line graphs. More specialized libraries like SageMath offer built-in functions for exact (\Delta + 1)-colorings using fan rotations, enabling efficient prototyping for graphs up to thousands of edges.[^[44]]

Complexity Results

Determining whether the chromatic index \chi'(G) of a simple graph G equals its maximum degree \Delta(G) is NP-complete in general.[^[30]] This hardness holds even when restricted to cubic graphs, where \Delta(G)=3, establishing that distinguishing Class 1 from Class 2 graphs is computationally intractable for this case.[^[30]] In contrast, certain graph classes admit polynomial-time algorithms for exact edge coloring. For bipartite graphs, König's theorem guarantees that \chi'(G)=\Delta(G), and an optimal coloring can be constructed in polynomial time by iteratively computing maximum matchings, with overall time complexity O(\Delta |E| \sqrt{|V|}) using Hopcroft-Karp or O(\Delta |E|) using more advanced methods.[^[45]] Despite the NP-hardness of exact computation, approximation algorithms provide efficient ways to obtain near-optimal edge colorings. For graphs with fixed maximum degree \Delta, deterministic polynomial-time algorithms exist that produce proper edge colorings using at most (1+\epsilon)\Delta colors for any constant \epsilon>0, with running time polynomial in the input size and $1/\epsilon.^[46] Randomized algorithms further improve this by achieving colorings with \Delta + O(\sqrt{\Delta}) colors with high probability, offering a multiplicative factor of $1 + O(1/\sqrt{\Delta}) relative to \Delta.^[47] From a parameterized complexity perspective, the edge coloring problem is fixed-parameter tractable when parameterized by the treewidth tw(G) of the graph. Dynamic programming over tree decompositions enables solving for \chi'(G) in time O(2^{O(tw \log tw)} n) or similar bounds, exploiting the structural sparsity of low-treewidth graphs.[^[48]]

References

[1]
[PDF] Section 17.2. Vizing's Theorem
Jul 8, 2022 · Note. Vizing's Theorem is due to Vadim Vizing and appears in “On an Estimate of the Chromatic Class of a p-Graph,” Diskret. Analiz.
[2]
[PDF] vizing's theorem and edge-chromatic graph theory
Aug 28, 2015 · Vizing's Theorem is the central theorem of edge-chromatic graph theory, since it provides an upper and lower bound for the chromatic index χ0(G ...
[3]
[PDF] A Constructive Proof of Vizing's Theorem - UT Computer Science
Vizing's Theorem. All the edges of a graph of maximum degree less than N can be colored using N colors so that the graph is valid. We call a color incident ...
[4]
[PDF] GRAPH THEORY WITH APPLICATIONS
GRAPH THEORY. WITH APPLICATIONS. J. A. Bondy and U. S. R. Murty. Depart,nent· of Combinatorics and Optimization,. University of Waterloo,. Ontario, Canada'.
[5]
Edge Coloring -- from Wolfram MathWorld
An edge coloring of a graph G is a coloring of the edges of G such that adjacent edges (or the edges bounding different regions) receive different colors.
[6]
Edge Chromatic Number -- from Wolfram MathWorld
The edge chromatic number, sometimes also called the chromatic index, of a graph G is fewest number of colors necessary to color each edge of G.
[7]
Maximum Vertex Degree -- from Wolfram MathWorld
The maximum degree, sometimes simply called the maximum degree, of a graph G is the largest vertex degree of G, denoted Delta.Missing: definition | Show results with:definition
[8]
Line Graph -- from Wolfram MathWorld
A graph with minimum vertex degree at least 5 is a line graph iff it does not contain any of the above six Metelsky graphs as an induced subgraph (Metelsky and ...
[9]
Chromatic Number -- from Wolfram MathWorld
By definition, the edge chromatic number of a graph G equals the chromatic number of the line graph L(G) . Brooks' theorem states that the chromatic number ...<|control11|><|separator|>
[10]
[PDF] APPENDIX A VIZING'S TWO FUNDAMENTAL PAPERS
Vizing, V. G. (1964). On an estimate of the chromatic class of a p-graph (in Russian). Diskret. Analiz, 3:25–30. 298. Vizing, V. G. (1965). The chromatic ...
[11]
König's Line Coloring Theorem -- from Wolfram MathWorld
König's line coloring theorem states that the edge chromatic number of any bipartite graph equals its maximum vertex degree.
[12]
[PDF] On Vizing's edge colouring question - arXiv
Jul 16, 2021 · The main result of this paper is based on the Vizing's fans; in his proof he only needs to handle ... A constructive proof of Vizing's theorem. In ...
[13]
[PDF] Download - Graph Coloring Methods
Between the statement of a lemma and its proof, we often include an informal proof sketch. (This sort of intuition is frequently provided in lectures, but ...
[14]
[PDF] A new tool for proving Vizing's Theorem - Alexandr V. Kostochka
Vizing, On an estimate of the chromatic class of a p-graph, Diskret. Anal. (3) (1964) 25–30 (in Russian). [7] V.G. Vizing, Critical graphs with given ...
[15]
[PDF] arXiv:2006.15703v3 [math.CO] 4 Mar 2021
Mar 4, 2021 · Lemma 4.8 (First fan lemma). Let ϕ be a partial proper coloring and let xy ∈ E \ dom(ϕ) be an uncolored edge. Then there exists a ϕ ...
[16]
https://arxiv.org/pdf/2107.07900
[17]
Coloring - Discrete Mathematics - An Open Introduction
The following statements are about the chromatic number χ ( G ) and the chromatic index χ ′ ( G ) of graphs. ... For any cycle, the chromatic index is equal to ...
[18]
[PDF] Bipartite edge-colouring in O(∆m) time - CWI
In a classical paper, König [9] showed that the edges of a bipartite graph G can be coloured with ∆(G) colours, where ∆(G) is the maximum degree of G. (In this ...
[19]
[PDF] The Hilton–Zhao Conjecture is True for Graphs with Maximum ...
May 18, 2019 · A simple graph G is overfull if |E(G)| > ∆⌊|V (G)| /2⌋. By the pigeonhole principle, every overfull graph G has χ′(G) > ∆. The core of a graph, ...
[20]
[PDF] 1) Let G = (V,E) be a graph, let u, v € V, and let n be a non-negative ...
Vizing's theorem states that every graph is either class I or class II. If x is a real number, [x] denotes the greatest integer less than or equal to x. (Recall ...
[21]
[PDF] Measures of edge-uncolorability of cubic graphs
Feb 23, 2017 · Thus, some authors adopt the most simple definition stating that a snark is a bridgeless cubic class 2 graph. Moreover, we remark that, in ...
[22]
Snark -- from Wolfram MathWorld
Snarks are therefore class 2 graphs. There are several definitions of snarks. Following Brinkmann et al. (2013), call a weak snark a cyclically 4-edge connected ...
[23]
Odd 2-factored snarks - ScienceDirect.com
A snark (cf. e.g. [23]) is a bridgeless cubic graph with chromatic index four (by Vizing's theorem the chromatic index of every cubic graph is either three ...
[24]
[PDF] Towards the Overfull Conjecture - arXiv
Sep 5, 2024 · The overfull conjecture on graphs of odd order and large minimum degree. ... Graph Edge Coloring: Vizing's Theorem and. Goldberg's Conjecture.
[25]
None
Summary of each segment:
[26]
The NP-Completeness of Edge-Coloring | SIAM Journal on Computing
We show that it is NP-complete to determine the chromatic index of an arbitrary graph. The problem remains NP-complete even for cubic graphs.
[27]
[PDF] Overfullness of critical class 2 graphs with a small core degree
The fan argument was introduced by Vizing [14,15] in his classic results on the upper bounds of chromatic indices. We will use multifans, a generalized version ...
[28]
[PDF] Edge Coloring of Graphs
Critical Graphs. G is critical (or ∆-critical) if χe(G) = ∆ + 1 and χe(G − e) ≤ ∆ for any edge e in G. 2-critical graphs are odd cycles. Criticality is ...
[29]
A sufficient condition for a plane graph with maximum degree 6 to be ...
A well-known conjecture of Vizing (the planar graph conjecture) states that every plane graph with maximum degree Δ ≥ 6 is edge Δ -colorable.
[30]
The planar edge-coloring theorem of Vizing in $O(n\log n)$ time
Jul 6, 2025 · In 1965, Vizing [Diskret. Analiz, 1965] showed that every planar graph of maximum degree \Delta\ge 8 can be edge-colored using \Delta ...
[31]
Every Planar Graph with Maximum Degree 7 Is of Class 1
This paper shows that, for planar graphs with maximum degree 7, Vizing's conjecture is true. Article PDF. Download to read the full article text ...Missing: seven one
[32]
A sufficient condition for a planar graph to be class 1 - ScienceDirect
Open archive. Abstract. We prove that every planar graph G with Δ = 6 is of Class 1 if it does not contain a 5-cycle with a chord. Previous article in issue
[33]
Edge Colorings of Planar Graphs without 6-Cycles with Two Chords
Discover the proof that planar graphs with a minimum degree of 6 and limited 6-cycle chords belong to class 1. Explore now!
[34]
[1702.07559] Remarks on planar edge-chromatic critical graphs
Feb 24, 2017 · The only open case of Vizing's conjecture that every planar graph with \Delta\geq 6 is a class 1 graph is \Delta = 6. We give a short proof of ...
[35]
https://link.springer.com/article/10.1007/s003730070009
[36]
https://www.sciencedirect.com/science/article/pii/S0304397507004720
[37]
Vizing's Theorem in Near-Linear Time
Jun 23, 2025 · The following lemma shows that we can always find a U-avoiding Vizing fan for a u-edge. Lemma 5.6. Given a u-edge e ∈ U, there exists a U ...
[38]
[PDF] ALGORITHMS FOR EDGE― COLORING GRAPHS H.N. Gabow T ...
irnplementation of the standard proof of Vizing's Theorem・ is introduced in Sec… tion 3. This algorithm colors the edges of an uncolored sirnple graph with d+1.
[39]
(PDF) A simple and fast heuristic algorithm for edge-coloring of graphs
Aug 7, 2025 · Vizing's theorem states that the edge coloring of a simple graph G requires either Δ \Delta or Δ + 1 \Delta+1 colors, where Δ \Delta is the ...
[40]
Edge Coloring Algorithms on Graphs PR #7397 - Google Groups
Apr 15, 2024 · We have implemented an algorithm for finding the edge coloring in a graph. It uses a technique similar to Misra & Gries Edge coloring algorithm.
[41]
Deterministic Simple $(Δ+\varepsilonα)$-Edge-Coloring in Near ...
Jan 19, 2024 · We devise a simple deterministic (1+\varepsilon)\Delta-edge-coloring algorithm with running time O\left(m\cdot\frac{\log n}{\varepsilon}\right).Missing: approximation | Show results with:approximation
[42]
Distributed Edge Coloring and a Special Case of the Constructive ...
We give a randomized edge coloring algorithm that can use palette sizes as small as Δ + Õ(√Δ), which is a natural barrier for randomized approaches.<|control11|><|separator|>
[43]
The parameterised complexity of list problems on graphs of ...
We have proved that List Edge Chromatic Number and List Total Chromatic Number are fixed parameter tractable, parameterised by treewidth, although the List Edge ...