We investigate some graph classes that lie on complexity dividing lines in computer science and show using that the lines hold when graphs are countably infinite. If graphs are finite, we may consider a class $\mathcal{C}^{\mathrm{fin}}$ complex if it is graph-isomorphism (GI) complete, which means that maximal time is needed to check if two graphs in the class are isomorphic. If graphs are allowed to be countable, we may consider a class $\mathcal{C}$ complex if it is universal under effective bi-interpretabilty, where one can effectively code any given countable graph as a graph in $\mathcal{C}$ while preserving the automorphism group of the graph. When restricting our study to $F$-free graphs, which are graphs that cannot embed a fixed finite graph $F$ as an induced subgraph, we show that if the GI problem is not solvable in polynomial time, then $\mathcal{C}^{\mathrm{fin}}$ is graph-isomorphism complete if and only if $\mathcal{C}$ is universal. There is significant room for future research. We may explore graph principles on $\mathcal{C}$, such as the principle of Ramsey’s theory for pairs, which asserts the existence of infinite cliques/anticliques in any countable graph. Using tools from reverse mathematics or Weihrauch reducibility, we may explore: Is finding infinite cliques/anticliques less computationally expensive over countable $F$-free graphs than over general countable graphs? How does this relate to the time-complexity of finding maximal cliques/anticliques on finite $F$-free graphs? This is joint work with Vittorio Cipriani, Ekaterina Fokina, Matthew Harrison-Trainor, and Dino Rossegger.