We study classes of countable graphs where every member does not contain a given finite graph as an induced subgraph -- denoted by $\mathsf{Free}(\mathcal{G})$ for a given finite graph $\mathcal{G}$. Our main results establish a structural dichotomy for such classes: If $\mathcal{G}$ is not an induced subgraph of $\mathcal{P}_4$, then $\mathsf{Free}(\mathcal{G})$ is on top under effective bi-interpretability, implying that the members of $\mathsf{Free}(\mathcal{G})$ exhibit the full range of structural and computational behaviors. In contrast, if $\mathcal{G}$ is an induced subgraph of $\mathcal{P}_4$, then $\mathsf{Free}(\mathcal{G})$ is structurally simple, as witnessed by the fact that every member satisfies the computable embeddability condition. This dichotomy is mirrored in the finite setting when one considers combinatorial and complexity-theoretic properties. Specifically, it is known that $\mathsf{Free}(\mathcal{G})^{fin}$ is complete for graph isomorphism and not a well-quasi-order under embeddability whenever $\mathcal{G}$ is not an induced subgraph of $\mathcal{P}_4$, while in all other cases $\mathsf{Free}(\mathcal{G})^{fin}$ forms a well-quasi-order and the isomorphism problem for $\mathsf{Free}(\mathcal{G})^{fin}$ is solvable in polynomial time.

翻译：我们研究一类可数图，其中每个成员均不包含给定有限图作为诱导子图——对于给定有限图 $\mathcal{G}$，记作 $\mathsf{Free}(\mathcal{G})$。我们的主要结果为此类图建立了一个结构性二分定理：若 $\mathcal{G}$ 不是 $\mathcal{P}_4$ 的诱导子图，则 $\mathsf{Free}(\mathcal{G})$ 在有效双可解释性下处于顶端，这意味着 $\mathsf{Free}(\mathcal{G})$ 的成员展现出全面的结构性与计算行为。相反，若 $\mathcal{G}$ 是 $\mathcal{P}_4$ 的诱导子图，则 $\mathsf{Free}(\mathcal{G})$ 在结构上较为简单，这体现为其每个成员均满足可计算嵌入条件。该二分性在考虑组合与计算复杂性性质时，在有限图设定中亦有对应表现。具体而言，已知当 $\mathcal{G}$ 不是 $\mathcal{P}_4$ 的诱导子图时，$\mathsf{Free}(\mathcal{G})^{fin}$ 对于图同构问题是完备的，且在嵌入关系下不构成良拟序；而在所有其他情况下，$\mathsf{Free}(\mathcal{G})^{fin}$ 构成良拟序，且 $\mathsf{Free}(\mathcal{G})^{fin}$ 的同构问题可在多项式时间内求解。