Testing C_k-freeness in Bounded Admissibility Graphs

We study $C_k$-freeness in sparse graphs from a property testing perspective, specifically for graph classes with bounded $r$-admissibility. Our work is motivated by the large gap between upper and lower bounds in this area: $C_k$-freeness is known to be testable in planar graphs [czumaj201], but not in graphs with bounded arboricity for $k > 3$ [Eden 2024]. There are a large number of interesting graph classes that include planar graphs and have bounded arboricity (\eg classes excluding a minor), calling for a more fine-grained approach to the question of testing $C_k$-freeness in sparse graph classes. One such approach, inspired by the work of Nesetril and Ossona de Mendez, is to consider the graph measure of $r$-admissibility, which naturally forms a hierarchy of graph families $\mathcal A_1 \supset \mathcal A_2 \supset \ldots \supset \mathcal A_\infty$ where $\mathcal A_r$ contains all graph classes whose $r$-admissibility is bounded by some constant. The family $\mathcal A_1$ contains classes with bounded arboricity, the class $\mathcal A_\infty$ contains classes like planar graphs, graphs of bounded degree, and minor-free graphs. Awofeso et al recently made progress in this direction. They showed that $C_4$- and $C_5$-freeness is testable in $\mathcal A_2$. They further showed that $C_k$-freeness is \emph{not} testable in $\mathcal A_{\lfloor k/2\rfloor -1}$ and conjectured that $C_k$-freeness is testable in $\mathcal A_{\lfloor k/2 \rfloor}$. In this work, we prove this conjecture: $C_k$-freeness is indeed testable in graphs of bounded $\lfloor k/2\rfloor$-admissibility.