Dichotomy results for classes of countable graphs

Abstract

We study classes of countable graphs where every member does not contain a given finite graph as an induced subgraph -- denoted by Free for a given finite graph . Our main results establish a structural dichotomy for such classes: If is not an induced subgraph of , then Free is on top under effective bi-interpretability, implying that the members of Free exhibit the full range of structural and computational behaviors. In contrast, if is an induced subgraph of , then Free 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 Free is complete for graph isomorphism and not a well-quasi-order under embeddability whenever is not an induced subgraph of , while in all other cases Free forms a well-quasi-order and the isomorphism problem for Free is solvable in polynomial time.