The homomorphism domination exponent

We initiate a study of the homomorphism domination exponent   of a pair of graphs FF and GG, defined as the maximum real number cc such that |Hom(F,T)|⩾|Hom(G,T)|c for every graph TT. The problem of determining whether HDE(F,G)⩾1 is known as the homomorphism domination problem  , and its decidability is an important open question arising in the theory of relational databases. We investigate the combinatorial and computational properties of the homomorphism domination exponent, proving upper and lower bounds and isolating classes of graphs FF and GG for which HDE(F,G) is computable. In particular, we present a linear program computing HDE(F,G) in the special case, where FF is chordal and GG is series–parallel.