graph_coloring (1122B)
1 # Graph coloring 2 3 ## Special cases 4 5 - [bipartite_graph] 6 - [3_coloring] 7 - [3_colorable] 8 9 ## Results 10 11 - [grotzschs_theorem]: 12 - [planar_graph] which has no [triangle] is 3-colorable 13 - [graph_coloring_greedy]: if a graph has maximal [degree] d then it has a coloring with d+1 colors at most ([greedy_algorithm]) 14 15 ## Conjectures 16 17 - [hadwiger_conjecture] 18 19 ## Variants 20 21 - [edge_coloring] 22 - [list_coloring] 23 - [graph_coloring_counting] 24 - [H_coloring] 25 - [Grundy_number] 26 27 ## Complexity 28 29 - [np_complete], already for [graph_planar] and [4_regular] graphs 30 - [np_complete] to find if it is 3 or 4 31 - 4 colors on [planar_graph] is always feasible by the [four_color_theorem] 32 - [3_coloring] is in [linear_time] by [Brook's_theorem] on [graphs] of maximal [degree] 3 33 - see https://cstheory.stackexchange.com/questions/51368/which-hypergraphs-can-be-simplified-by-alternatively-removing-a-hyperedge-and-an 34 - [bipartiteness_testing] (k=2) 35 36 ## References 37 38 "Graph Coloring Methods" book: https://graphcoloringmethods.com/ 39 40 Up: [graph_problem] 41 42 See also: [chromatic_number], [graph_colorability] 43 44 Aliases: graph colored, k coloring