Jiřı Fiala1
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.