edge_coloring (671B)
1 # Edge coloring 2 3 A function mapping the [edges] of an [undirected_graph] to colors such that no two incident edges get the same color 4 5 An easy lower bound on the number of colors required is the [maximum_degree] 6 7 [Vizings_theorem]: the number of colors needed is always at most the [maximum_degree] plus one 8 9 It is [NP_hard] to determine which of the two applies 10 11 Computing edge colorings whose number of colors is the [maximum_degree] plus one can now be done in [near_linear_time] 12 13 - [incremental_maintenance_edge_coloring] 14 - [2_edge_coloring] 15 - [online_edge_coloring] 16 17 Up: [graph_coloring] 18 19 Aliases: edge colored 20 21 See also: [graph_edge_colored], [graph_factorization]