wiki_research

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

graph_homomorphism_problem (426B)

      1 # Graph homomorphism problem
      2 
      3 The *graph homomorphism problem* is the [decision_problem] that asks, given two [graphs] G and H, whether there exists a [homomorphism] from G to H
      4 
      5 The problem is [NP_complete] even if the right-hand-side [graph] H is fixed, e.g., to a [triangle] (because it amounts to [deciding] [3_colorability] of G
      6 
      7 Up: [decision_problem], [graph_homomorphism]
      8 
      9 See also: [CSP], [graph_isomorphism_problem]