Vi studerar kraften i fyra frågemodeller i samband med egenskapstestning i allmänna grafer, där vår huvudsakliga fallstudie är problemet med att testa k-färgbarhet. Två frågetyper, som har studerats i stor utsträckning i det förflutna, är par frågor och grannar frågor. Den förra motsvarar att fråga om det finns en kant mellan någon viss par hörn, och den senare att be om den i'th granne till en viss vertex. Vi visar att medan för par frågor, testa k-färgbarhet kräver ett antal frågor som är en monoton minskande funktion i genomsnitt grad d, frågekomplexet i fallet med grannen frågor fortfarande ungefär samma för varje densitet och för stora värden av k. Vi anser också en kombinerad modell som tillåter båda typerna av frågor, och vi föreslår en ny, starkare, frågemodell, som är relaterad till fältet Grupptest. Vi ger ett ensidigt fel övre och nedre gränser för alla modeller, där gränserna är nästan snäva för tre av modellerna. I vissa fall sträcker sig våra nedre gränser till tvåsidiga felalgoritmer. Problemet med att testa k-färgbarhet studerades tidigare i samband med täta och glesa grafer, och i våra bevis förenar vi strategier från dessa fall, och ger också några nya verktyg och tekniker som kan vara av oberoende intresse.
Ben-Eliezer m.fl. studerade styrkan hos olika frågetyper i samband med egenskapstestning i allmän graf REF.
Comparing the strength of query types in property testing: the case of testing k-colorability
{'venue': "SODA '08", 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}