Testing Induced-Subgraph Freeness in Outerplanar Graphs under the Random-Neighbor Oracle

Pan Peng, Kefan Yu

We prove that, for every fixed nonempty graph $H$, induced-$H$-freeness is testable with ${\epsilon }^{-O_H(1)}$ queries on outerplanar graphs with no maximum-degree bound in the $…