# Graph orders arising from locally constrained homomorphisms

Charles University, Prague

Degree refinement matrices have tight connections to graph homomorphisms
that locally, on the neighborhoods of a vertex and its image, are
constrained to three types: bijective, injective or surjective. If graph
has a homomorphism of given type to graph , then we say that the
degree refinement matrix of is smaller than that of . This way we
obtain three partial orders. We present algorithms that will determine
whether two matrices are comparable in these orders. For the bijective
constraint no two distinct matrices are comparable. For the injective
constraint we give a PSPACE algorithm, which we also apply to disprove a
conjecture on the equivalence between the matrix orders and universal
cover inclusion.

#### Footnotes

- ... Fiala
^{1}
- joint work with Daniël Paulusma and Jan Arne Telle

2005-05-23