Permutation graph subsets See here.
Can permutation graphs (PG) be arbitrarily complex, in the sense that for any $n$, there is a non-PG $N_n$, such that all smaller subgraphs of $N_n$ are PG?
(In contrast to, say, all planar graphs: any non-planar graph will contain $K_{3,3}$ or $K_5$, a finite list.)
 A: The odd cycles $C_5, C_7, C_9, C_{11},\dots$ are an infinite list of graphs that are not permutation graphs (because they're not perfect), whose every subgraph is a permutation graph. (The subgraphs are all unions of paths, and it's not hard to realize a path as a permutation graph.) Therefore permutation graphs are "arbitrarily complex" in this sense.
I would argue that thinking about subgraphs is not the right framework for permutation graphs to begin with, though, because a subgraph of a permutation graph is not necessarily a permutation graph itself, either. (In particular, every graph is a subgraph of some complete graph, which is a permutation graph.)

Relatedly, Gallai's 1967 paper Transitiv orientierbare Graphen characterizes the permutation graphs in terms of an infinite forbidden list of induced subgraphs. (This is not directly comparable to Kuratowski's or Wagner's characterization of planar graphs; in fact, I would argue that planar graphs are more complicated, because they forbid all subdivisions (or minors) of $K_{3,3}$ and $K_5$.)
One of the consequences of Gallai's characterization is that even cycles $C_6, C_8, C_{10}, \dots$ are also not permutation graphs, in addition to the odd cycles mentioned earlier.
Gallai's paper is not accessible online and is also in German, but his characterization is cited as Theorem 4.3 in this paper, which describes the forbidden subgraphs.
