Vi studerar graf egenskaper som är testbara för avgränsade grad grafer i tid oberoende av indatastorleken. Vårt mål är att skilja mellan grafer som har en förutbestämd graf egenskap och grafer som är långt ifrån varje graf som har den egenskapen. Man tror att nästan alla, även mycket enkla grafegenskaper kräver en stor komplexitet för att testas för godtyckliga (begränsad grad) grafer. Därför fokuserar vi i detta papper på att testa grafegenskaper för speciella klasser av grafer. Vi kallar en graf familj icke-expandera om varje graf i denna familj har en svag expansion (dess expansion är O(1/ log 2 n), där n är grafstorleken). En graf familj är ärftlig om det är stängt under vertex avlägsnande. På samma sätt är en graf egenskap ärftlig om den är stängd under vertex borttagning. Vi kallar en graf egenskap Π att vara testbar för en graf familj F om för varje graf G  och F, i tid oberoende av storleken på G vi kan skilja mellan fallet när G satis es egenskap Π och när det är långt från varje graf tillfredsställande egenskap Π. I detta papper bevisar vi att i den avgränsade grad grafen modellen, någon ärftlig egenskap kan testas om indatagrafen tillhör en ärftlig och icke-expanderande familj av grafer. Som en ansökan, vårt resultat innebär till exempel att någon ärftlig egenskap (t.ex., k-färgbarhet, H-frihet, etc.) kan testas i den begränsade gradgrafmodellen för plana grafer, grafer med avgränsat släkte, intervallgrafer, etc. Inga sådana resultat har varit kända tidigare, och före vårt arbete, har mycket få grafegenskaper varit kända för att vara testbara för allmänna grafklasser i den avgränsade grad grafmodellen.
Czumaj-Sohler-Shapira visade att ärftliga egenskaper hos icke-expanderande grafer är testerbara REF.
Testing hereditary properties of non-expanding bounded-degree graphs
{'venue': 'Electronic Colloquium on Computational Complexity', 'journal': 'Electronic Colloquium on Computational Complexity (ECCC)', 'mag_field_of_study': ['Mathematics', 'Computer Science']}