Results on H-Freeness Testing in Graphs of Bounded r-Admissibility

We proceed in this line of research by using the $r$-admissibility measure that originates from the field of structural sparse graph theory. Graphs of bounded $1$-admissibility are identical to graphs of bounded arboricity, while graphs of bounded degree, planar graphs, graphs of bounded genus, and even graphs excluding a fixed graph as a (topological) minor have bounded $r$-admissibility for any value of $r$ [Nešetřil and Ossona de Mendez, 2012]. In this work we show that $H$-freeness is testable in graphs with bounded $2$-admissibility for all graphs $H$ of diameter $2$. Furthermore, we show the testability of $C_4$-freeness in bounded $2$-admissible graphs directly (with better query complexity) and extend this result to $C_5$-freeness. Using our techniques it is also possible to show that $C_6$-freeness and $C_7$-freeness are testable in graphs with bounded $3$-admissibility. The formal proofs will appear in the journal version of this paper.

These positive results are supplemented with a lower bound showing that, for every $r \geq 4$, $C_r$-freeness is not testable for graphs of bounded $(\lfloor r/2 \rfloor - 1)$-admissibility. This lower bound will appear in the journal version of this paper. This implies that, for every $r > 0$, there exists a graph $H$ of diameter $r+1$, such that $H$-freeness is not testable on graphs with bounded $r$-admissibility. These results lead us to the conjecture that, for every $r > 4$, and $t \leq 2r+1$, $C_t$-freeness is testable in graphs of bounded $r$-admissibility, and for every $r > 2$, $H$-freeness for graphs $H$ of diameter $r$ is testable in graphs with bounded $r$-admissibility.