Understanding lettericity I: a structural hierarchy

Abstract

Lettericity is a graph parameter introduced by Petkovšek in 2002 in order to study well-quasi-orderability under the induced subgraph relation. In the world of permutations, geometric griddability was independently introduced in 2013 by Albert, Atkinson, Bouvel, Ruškuc and Vatter, partly as an enumerative tool. Despite their independent origins, those two notions share a connection: they highlight very similar structural features in their respective objects. The fact that those structural features arose separately on two different occasions makes them very interesting to study in their own right. In the present paper, we explore the notion of lettericity through the lens of "minimal obstructions", i.e., minimal classes of graphs of unbounded lettericity, and identify an infinite collection of such classes. We also discover an intriguing structural hierarchy that arises in the study of lettericity and that of griddability.