2026-08-06T00:52:26Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:23392 2025-10-02T12:53:53Z ddc:004 open_access

Testing C_k-Freeness in Bounded Admissibility Graphs Awofeso, Christine Greaves, Patrick Lachish, Oded Levi, Amit Reidl, Felix Property Testing Sparse Graphs Cycle Admissibility 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 [Czumaj and Sohler, 2019], but not in graphs with bounded arboricity for k > 3 [Talya Eden et al., 2024]. There are a large number of interesting graph classes that include planar graphs and have bounded arboricity (e.g. 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 [Nešetřil and {Ossona de Mendez}, 2012], is to consider the graph measure of r-admissibility, which naturally forms a hierarchy of graph families A₁ ⊃ A₂ ⊃ … ⊃ A_∞ where A_r contains all graph classes whose r-admissibility is bounded by some constant. The family A₁ contains classes with bounded arboricity, the class A_∞ contains classes like planar graphs, graphs of bounded degree, and minor-free graphs. Awofeso ηl [Awofeso et al., 2025] recently made progress in this direction. They showed that C₄- and C₅-freeness is testable in A₂. They further showed that C_k-freeness is not testable in A_{⌊k/2⌋ -1} and conjectured that C_k-freeness is testable in A_{⌊k/2⌋}. In this work, we prove this conjecture: C_k-freeness is indeed testable in graphs of bounded ⌊k/2⌋-admissibility. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Christine Awofeso and Patrick Greaves and Oded Lachish and Amit Levi and Felix Reidl 2025 Is Part Of LIPIcs, Volume 334, 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2025.15 urn:nbn:de:0030-drops-233926 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2025.15 eng https://creativecommons.org/licenses/by/4.0/legalcode