wiki_research

personal research wiki
git clone https://a3nm.net/git/wiki_research/
Log | Files | Refs

graph_coloring (1110B)


      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