2026-09-10T09:44:27Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:27752 2026-09-09T12:19:36Z ddc:004 open_access

Towards Tight Bounds for Testing k-Colorability Kushnir, Nick Shapira, Asaf k-colorability property testing sample complexity graph property testing random graphs Determining the sample complexity for testing k-colorability is perhaps the most well studied problem in property testing. It was (implicitly) introduced almost 50 years ago by Bollobás, Erdős, Simonovits and Szemerédi, who used the regularity lemma in order to give a tower-type bound for this problem. This bound has been successively improved in a long list of works, bringing the state-of-the-art bounds to lie between Ω(1/ε) and O((k/ε)log²(1/ε)). We obtain the following new results: ii) Our first main result is an improved O((k/ε)log(1/ε)) upper bound, bringing the sample complexity closer to "truly" linear in ε. To prove this result, we improve upon a variant of the container method, introduced recently in the breakthrough paper of Blais and Seth. iii) Perhaps the most important gap in our understanding of this problem is that while the best known upper bound increases with k, the lower bound is independent of k. Our second main result fills this gap by providing a new Ω((log k)/ε) lower bound, improving upon a result of Alon and Krivelevich from 2002. We conjecture that this is the true sample complexity of k-colorability. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Nick Kushnir and Asaf Shapira 2026 Is Part Of LIPIcs, Volume 392, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.APPROX/RANDOM.2026.35 urn:nbn:de:0030-drops-277523 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2026.35 eng https://creativecommons.org/licenses/by/4.0/legalcode