graph_coloring (1048B)
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 25 ## Complexity 26 27 - [np_complete], already for [graph_planar] and 4-regular graphs 28 - [np_complete] to find if it is 3 or 4 29 - knowing if it is 2 is [graph_bipartite] hence [ptime]-testable 30 - 4 colors is always feasible by the [four_color_theorem] 31 - [3_coloring] is in [linear_time] by [Brook's_theorem] on [graphs] of maximal [degree] 3 32 - see https://cstheory.stackexchange.com/questions/51368/which-hypergraphs-can-be-simplified-by-alternatively-removing-a-hyperedge-and-an 33 34 ## References 35 36 "Graph Coloring Methods" book: https://graphcoloringmethods.com/ 37 38 Up: [graph_problem] 39 40 See also: [chromatic_number]