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 $\mathfrak{ H}$ and a finite set of pathographs $\mathcal{ F}$, is there an $\mathcal{ F}$-free realization of $\mathfrak{ 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\subseteq S'$? We prove the pathograph realization problem is undecidable in general, but it is decidable in the case that $\mathfrak{ H}$ has no rungs (but may have spokes), or if $\mathcal{ F}$ is closed under adding edges, spokes, and rungs. We also discuss some potential applications to proving decomposition theorems.

Categories: math.CO cs.DM cs.DS

Pathographs and some (un)decidability results