Homomorphic equivalence

In graph theory, a branch of mathematics, two graphs G and H are called homomorphically equivalent if there exists a graph homomorphism ${\displaystyle f\colon G\to H}${\displaystyle f\colon G\to H} and a graph homomorphism ${\displaystyle g\colon H\to G}${\displaystyle g\colon H\to G}. An example usage of this notion is that any two cores of a graph are homomorphically equivalent.

Homomorphic equivalence also comes up in the theory of databases. Given a database schema, two instances I and J on it are called homomorphically equivalent if there exists an instance homomorphism ${\displaystyle f\colon I\to J}${\displaystyle f\colon I\to J} and an instance homomorphism ${\displaystyle g\colon J\to I}${\displaystyle g\colon J\to I}.

Deciding whether two graphs are homomorphically equivalent is NP-complete.^[1]

In fact for any category C, one can define homomorphic equivalence. It is used in the theory of accessible categories, where "weak universality" is the best one can hope for in terms of injectivity classes; see ^[2]

• Graph theory
• Equivalence (mathematics)
• Graph theory stubs

• Articles needing additional references from August 2016
• All articles needing additional references
• All stub articles