vizings_theorem (810B)
1 # Vizing's theorem 2 3 https://en.wikipedia.org/wiki/Vizing%27s_theorem 4 5 If an [undirected_graph] has [maximal_degree] d then it can be [edge_colored] with at most d+1 colors, in time O(mn) 6 7 high-level explanation of the algorithm in [polynomial_times], https://simons.berkeley.edu/media/28058/download?attachment p17 8 - uses [Eulerian_partitioning] 9 - easier to get a d+3 coloring 10 11 A graph is called [class_1] if it can be edge-colored with exactly d colors, and [class_2] otherwise. It is [NP_complete] to decide if a graph is [class_1], cf [holyer1981np], even for [simple_cubic_graphs] 12 - and [leven1983np] for other degrees 13 14 Such a coloring can be computed in time O(m log d) with high probability, cf [assadi2025vizing] 15 16 Up: [theorem] on [edge_coloring] 17 18 See also: [graph_coloring_greedy], [1_factorization]