Partially ordering finite graphs

Question

What are some interesting partial orders on the set of all finite graphs (identified up to isomorphism), apart from the usual (induced) subgraph relation and the (topological) minor relation, and why are they interesting?

Answer 1

"interesting" is subjective, but you could come up with several examples of partial orders (or total orders for that matter).

For example $\preceq_{\omega}$ which I define as $G\preceq_{\omega} H$ iff $\omega(G)\leq \omega(H)$ (where $\omega(G)$ denotes the clique number of the graph $G$, i.e. the maximal number of vertices in a complete subgraph of $G$)

Note that $\subseteq$ (the subgraph relation) is a subset of $\preceq_{\omega}$. That is to say, if $G\subseteq H$ then $G\preceq_{\omega} H$. The proof of which should be clear since if $K$ is a maximal clique of $G$ with $|K|=\omega(G)$, then $K\subseteq G\subseteq H$ and so $H$ has $K$ as a complete subgraph implying $\omega(H)\geq |K|=\omega(G)$. It is also worth noting that this is a total order, unlike $\subseteq$, since all graphs can be compared.

You might try also playing with the similar idea of using instead $\alpha(G)$, the independence number of a graph and see how that relates to the subgraph relation.