Pathographs and some (un)decidability results

We introduce pathographs as a framework to study graph classes defined by forbidden structures, including forbidding induced subgraphs, minors, etc. Pathographs approximately generalize s-graphs of L\'ev\^eque--Lin--Maffray--Trotignon by the addition of two extra adjacency relations: one between subdivisible edges and vertices called spokes, and one between pairs of subdivisible edges called rungs. We consider the following decision problem: given a pathograph H and a finite set of pathographs F, is there an F-free realization of H? This may be regarded as a generalization of the "graph class containment problem": given two graph classes S and $S'$, is it the case that S⊆ S'? We prove the pathograph realization problem is undecidable in general, but it is decidable in the case that H has no rungs (but may have spokes), or if F is closed under adding edges, spokes, and rungs. We also discuss some potential applications to proving decomposition theorems.