hence solving this problem is expected to be hard. But if we are

given a promise that the graph is either k-colorable of `far from

being k-coloarble', then can we make some intelligent deductions `quickly'

In fact we want to answer this in sublinear time - without even looking at

the entire input. The efficiency of such an algorihtm is measured by the

number of input bits read. Property Testing deals with designing such

algorithms that can correctly answer (with high probability) by looking at

a small fraction of the input. In the past two decades this area has been in

the forefront of research in theoretical computer science - we will take a

look at it.