{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,30]],"date-time":"2026-04-30T03:35:54Z","timestamp":1777520154628,"version":"3.51.4"},"reference-count":24,"publisher":"Cambridge University Press (CUP)","issue":"4","license":[{"start":{"date-parts":[[2015,2,2]],"date-time":"2015-02-02T00:00:00Z","timestamp":1422835200000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Combinator. Probab. Comp."],"published-print":{"date-parts":[[2015,7]]},"abstract":"<jats:p>A graph on <jats:italic>n<\/jats:italic> vertices is \u03b5-far from a property <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S0963548314000765_inline1\"\/><jats:tex-math>$\\mathcal{P}$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> if one has to add or delete from it at least \u03b5<jats:italic>n<\/jats:italic><jats:sup>2<\/jats:sup> edges to get a graph satisfying <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S0963548314000765_inline1\"\/><jats:tex-math>$\\mathcal{P}$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>. A graph property <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S0963548314000765_inline1\"\/><jats:tex-math>$\\mathcal{P}$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> is strongly testable if for every fixed \u03b5 &gt; 0 it is possible to distinguish, with one-sided error, between graphs satisfying <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S0963548314000765_inline1\"\/><jats:tex-math>$\\mathcal{P}$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> and ones that are \u03b5-far from <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S0963548314000765_inline1\"\/><jats:tex-math>$\\mathcal{P}$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> by inspecting the induced subgraph on a random subset of at most <jats:italic>f<\/jats:italic>(\u03b5) vertices. A property is easily testable if it is strongly testable and the function <jats:italic>f<\/jats:italic> is polynomial in 1\/\u03b5, otherwise it is hard. We consider the problem of characterizing the easily testable graph properties, which is wide open, and obtain several results in its study. One of our main results shows that testing perfectness is hard. The proof shows that testing perfectness is at least as hard as testing triangle-freeness, which is hard. On the other hand, we show that being a cograph, or equivalently, induced <jats:italic>P<\/jats:italic><jats:sub>3<\/jats:sub>-freeness where <jats:italic>P<\/jats:italic><jats:sub>3<\/jats:sub> is a path with 3 edges, is easily testable. This settles one of the two exceptional graphs, the other being <jats:italic>C<\/jats:italic><jats:sub>4<\/jats:sub> (and its complement), left open in the characterization by the first author and Shapira of graphs <jats:italic>H<\/jats:italic> for which induced <jats:italic>H<\/jats:italic>-freeness is easily testable. Our techniques yield a few additional related results, but the problem of characterizing all easily testable graph properties, or even that of formulating a plausible conjectured characterization, remains open.<\/jats:p>","DOI":"10.1017\/s0963548314000765","type":"journal-article","created":{"date-parts":[[2015,2,2]],"date-time":"2015-02-02T08:41:23Z","timestamp":1422866483000},"page":"646-657","source":"Crossref","is-referenced-by-count":23,"title":["Easily Testable Graph Properties"],"prefix":"10.1017","volume":"24","author":[{"given":"NOGA","family":"ALON","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"JACOB","family":"FOX","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"56","published-online":{"date-parts":[[2015,2,2]]},"reference":[{"key":"S0963548314000765_ref8","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-005-0012-8"},{"key":"S0963548314000765_ref23","first-page":"939","volume-title":"Combinatorics II: Keszthely 1976","author":"Ruzsa","year":"1978"},{"key":"S0963548314000765_ref22","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539793255151"},{"key":"S0963548314000765_ref21","doi-asserted-by":"publisher","DOI":"10.1112\/jlms\/s1-28.1.104"},{"key":"S0963548314000765_ref14","doi-asserted-by":"publisher","DOI":"10.1145\/285055.285060"},{"key":"S0963548314000765_ref19","first-page":"19","volume-title":"Proc. Eighth Annual ACM\u2013SIAM Symposium on Discrete Algorithms","author":"McConnell","year":"1997"},{"key":"S0963548314000765_ref24","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(74)90063-X"},{"key":"S0963548314000765_ref1","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.10056"},{"key":"S0963548314000765_ref6","doi-asserted-by":"publisher","DOI":"10.1002\/9780470277331"},{"key":"S0963548314000765_ref10","doi-asserted-by":"publisher","DOI":"10.1007\/s00039-012-0171-x"},{"key":"S0963548314000765_ref9","doi-asserted-by":"publisher","DOI":"10.4007\/annals.2006.164.51"},{"key":"S0963548314000765_ref15","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.10078"},{"key":"S0963548314000765_ref2","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1994.1005"},{"key":"S0963548314000765_ref3","doi-asserted-by":"publisher","DOI":"10.1007\/s004930070001"},{"key":"S0963548314000765_ref4","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548306007759"},{"key":"S0963548314000765_ref5","doi-asserted-by":"publisher","DOI":"10.1137\/06064888X"},{"key":"S0963548314000765_ref7","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.32.12.331"},{"key":"S0963548314000765_ref11","doi-asserted-by":"publisher","DOI":"10.2307\/1969503"},{"key":"S0963548314000765_ref12","doi-asserted-by":"publisher","DOI":"10.4007\/annals.2011.174.1.17"},{"key":"S0963548314000765_ref13","doi-asserted-by":"publisher","DOI":"10.1007\/BF02020961"},{"key":"S0963548314000765_ref18","doi-asserted-by":"publisher","DOI":"10.1080\/01621459.1963.10500830"},{"key":"S0963548314000765_ref17","doi-asserted-by":"publisher","DOI":"10.1016\/S0012-365X(98)00183-6"},{"key":"S0963548314000765_ref20","volume-title":"Perfect Graphs","author":"Ram\u00edrez-Alfons\u00edn","year":"2001"},{"key":"S0963548314000765_ref16","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-97881-4"}],"container-title":["Combinatorics, Probability and Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0963548314000765","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,4,20]],"date-time":"2019-04-20T18:52:15Z","timestamp":1555786335000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0963548314000765\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,2,2]]},"references-count":24,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2015,7]]}},"alternative-id":["S0963548314000765"],"URL":"https:\/\/doi.org\/10.1017\/s0963548314000765","relation":{},"ISSN":["0963-5483","1469-2163"],"issn-type":[{"value":"0963-5483","type":"print"},{"value":"1469-2163","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,2,2]]}}}