The micro-world of cographs

NEW

Problem: Interpreting the quoted question literally: finite simple graphs are ordered by the induced-subgraph relation, and a “class” is any isomorphism-closed set of such graphs. A class is wqo/bqo when this induced-subgraph quasi-order is wqo/bqo in the Nash-Williams barrier sense. The wording is ambiguous: if “class” was intended to mean “hereditary class,” that is an extra hypothesis not present in the quoted sentence.

Result: The literal statement is false.

Let $R=\{(i,j)\in\mathbb N^2:i<j\}$ with

This is Rado’s standard wqo that is not bqo. It is wqo because in any infinite sequence $(a_n,b_n)$, either some later $a_m>b_0$, giving $(a_0,b_0)\preceq(a_m,b_m)$, or the $a_n$’s are bounded infinitely often, so one value $a$ occurs infinitely often and then the corresponding $b$’s contain a nondecreasing pair. It is not bqo because the map

is bad on the barrier $[\mathbb N]^2$: for $i<j<k$,

Now enumerate $R=\{r_0,r_1,\dots\}$. For each $r\in R$, let $T_r$ be the cycle $C_{n+3}$ where $r=r_n$. Cycles $C_m,C_n$, $m,n\ge3$, are incomparable under induced subgraph unless $m=n$.

For $r\in R$, let

which is finite, and define

Let

For finite $A,B\subseteq R$,

because each connected cycle component must embed into an isomorphic cycle component. Hence

Thus $(\mathcal G,\le_{\mathrm{ind}})$ is order-isomorphic to $R$. Therefore $\mathcal G$ is wqo but not bqo.

So not every wqo class of graphs is bqo, under the literal formulation. The counterexample is not hereditary; indeed its hereditary closure contains all cycles $C_n$, an infinite induced-subgraph antichain.

Citation: No external theorem is needed for the graph counterexample. The auxiliary order is the classical Rado wqo-not-bqo example; see R. Rado, “Partial well-ordering of sets of vectors,” Mathematika 1 (1954), 89–95, and Nash-Williams’s bqo theory.