Letter graphs and well-quasi-order by induced subgraphs (Q1349106)

All graphs \(G= (V,E)\) considered in this paper are undirected and simple ones. For a given word \(w\) over an alphabet and a set of ordered pairs of letters which define adjacencies the letter graph of \(w\) is constructed. Such graphs \(G\) over some alphabet of size \(k\) are called \(k\)-letter graphs. The lettericity \(\ell(G)\) of a graph \(G\) is the least size of the alphabet that suffices to represent \(G\) as a letter graph. The cycle \(C_6\) is given as a 3-letter graph with \(\ell(C_6)\leq 3\). In Chapter 3 the author gets basic properties of \(k\)-letter graphs, especially necessary and sufficient conditions for \(G\) to be a \(k\)-letter graph (Proposition 1), and from this it follows that 2-letter graphs are bipartite, split, or cobipartite graphs. In Chapter 4 cobipartite 2-letter graphs are characterized as unbounded interval graphs and split 2-letter graphs as threshold graphs, and from these results follows that the class of 2-letter graphs consists of threshold graphs, unbounded interval graphs, and their complements. Further, the author proves that 2-letter graphs can be recognized in polynomial time. Chapter 5 yields the following statements about the values of the lettericities \(\ell\) for cycles \(C_n\) and paths \(P_n\), namely (1) \(\ell(C_n)= \lfloor(n+ 4)/3\rfloor\) for \(n\geq 4\); (2) \(\lfloor(n+ 1)/3\rfloor\leq \ell(P_n)\leq \lfloor(n+4)/3)\rfloor\). The following is conjectured: If \(n\geq 3\) then \(\ell(P_n)= \lfloor(n+ 4)/3\rfloor\). It is proved that for large \(n\) there are \(n\)-vertex graphs whose lettericity exceeds \(0,707\cdot n\). In the final Chapter 6 it is shown that the class of \(k\)-letter graphs is well-quasi-ordered by the induced subgraph relation, and that it has a finite set of minimal forbidden induced subgraphs. Further, it is proved that for any fixed \(k\) the class of \(k\)-letter graphs can also be recognized in polynomial time. Three open problems are formulated.