8
$\begingroup$

For graphs $F$ and $G$, let $\hom(F,G)$ denote the number of homomorphisms (adjacency preserving maps) from $F$ to $G$. Define a relation $\le_{\hom}$ on (isomorphism classes of) graphs as $G \le_{\hom} H$ if $\hom(F,G) \le \hom(F,H)$ for all graphs $F$. This relation is clearly reflexive and transitive, and it is anti-symmetric by a result of Lovász. Thus $\le_{\hom}$ is a partial order on isomorphism classes of graphs. This partial order sits somewhere in between the subgraph partial order and the usual homomorphism (pre-)order in the sense that

$$G \text{ is a subgraph of } H \ \ \Longrightarrow \ \ G \le_{\hom} H \ \ \Longrightarrow \ \ G \text{ has a homomorphism to } H,$$

but neither of these implications can be reversed.

I am curious if this partial order has ever been considered in the literature before, and if so what is known about it.

Improve this question
$\endgroup$
2
  • $\begingroup$ Is it clear how many graphs one needs to test to check whether $G\leq_{hom} H$, e.g., if both have $n$ vertices? For example, if $G$ is the star on four vertices and $H$ is the union of a triangle $C_3$ and an isolated vertex, then $\hom(C_3, G)=0$, $\hom(C_3, H)=6$ but $\hom(G, G)=30$ and $\hom(G, H)=24$, so $G$ and $H$ are not comparable. $\endgroup$
    – Martin Rubey
    Commented Jan 25, 2023 at 17:17
  • 3
    $\begingroup$ @MartinRubey It is not even clear to me if determining whether $G \le_{hom} H$ is a decidable problem. $\endgroup$
    – David Roberson
    Commented Jan 25, 2023 at 19:17

0

Reset to default

You must log in to answer this question.