I am completely bamboozled by this problem, and although I believe the answer 'should' be yes, I cannot prove it for love nor money! I'll provide a couple of definitions for clarity's sake.
A $k$-letter graph $G$ is a graph defined by a finite word $x_{1}x_{2}...x_{n}$ over an alphabet $X$ of size $k$ together with a subset $S\subseteq{X^2}$ such that:
- $V(G)$ = {$1,2,...,n$}
- $E(G)$ = {$ij$ : $i\leq{j}$ and $(x_{i},x_{j})\in{S}$}
Note that $V(G)$ and $E(G)$ are the vertex-set and edge-set of $G$, and that $G$ is simple and undirected.
Also a hereditary class of graphs being finitely defined means that the set of minimal induced forbidden subgraphs for this class is finite.
I have a few ideas floating around, but not only are they hard to put into words, they don't appear to help. I spent all my energy trying to prove that the answer is yes, and have given little consideration to the possibility that the answer is no.
Many thanks.
Suppose that $H$ is a minimal forbidden induced subgraph for $k$-letter graphs. If we delete a vertex $v$, the result $H-v$ must be a $k$-letter graph; otherwise, $H-v$ would also be a forbidden induced subgraph, and $H$ would not be minimal.
We can use this to show that $H$ is a $(2k+1)$-letter graph. First, take a description of $H-v$ as a $k$-letter graph with alphabet $X$, word $x_1 x_2 \dots x_n$, and relation $S$. Define a new alphabet $X'$ which has two letters $x^+$ and $x^-$ for every $x \in S$, as well as one extra letter I'll just call $q$ for no reason.
For $i=1, \dots, n$, replace $x_i$ by $x_i^+$ if the $i^{\text{th}}$ vertex of $H-v$ is adjacent to $v$, and $x_i^-$ otherwise, getting a word over $X'$. Then, append $q$ to the end of this word. Define a new relation $S'$ with four pairs $(x^{\pm}, y^{\pm})$ for every pair $(x,y) \in S$, as well as the $k$ pairs $(x^+, q)$ for $x \in X$. The resulting alphabet, word, and relation define $H$ as a letter graph.
So all minimal forbidden induced subgraphs are $(2k+1)$-letter graphs; now we will show that there are finitely many.
First of all, there are only finitely many relations $S$: only the piddling, insignificant amount of $2^{(2k+1)^2}$. (We assume a fixed alphabet $X$, since it doesn't really matter what the letters are called.) For each choice of $S$, if $H_1$ is a $(2k+1)$-letter graph defined by $S$, $X$, and a word $w$, and $H_2$ is a $(2k+1)$-letter graph defined by $S$, $x$, and a subword of $w$, then $H_2$ is an induced subgraph of $H_1$, so both of them cannot be minimal forbidden subgraphs.
But by Higman's lemma, we can only pick finitely many words over $X$ without including a word and its subword. This means that for every relation $S$, there are finitely many minimal forbidden induced subgraphs defined with that relation.