Comment by ColinWright

No, that is not the case. The process does not rely on a third party.

Person A provides person B with the graph.

Person B claims to have coloured it.

Person A demands that they prove it.

Person B hides the colouring

Repeatedly:

* Person A points at an edge

* Person B reveals that the endpoints are differently coloured

* Person B re-hides the colouring and permutes the colours

If person B does not have a colouring, with probability 1 this process will fail and person A will know that person B does not have a colouring.

But if person B does have a colouring then each step will succeed, and by repeating the process person A can achieve any desired degree of confidence that person B must, indeed, have a colouring.

This process can be made digital rather than physical, and no third party need be involved. As a sketch of one step:

* Person B colours the graph

* For each vertex, person B generates a long random string, pre-pends the colour, applies a cryptographically strong hash function to that, and sends the result to A. This "Fixes and hides" the colouring

* Person A asked for two "colours" to be revealed

* Person B provide the associated "colour and random string"s, the pre-images of the requested hashes

* Person A checks the hashes and now knows the colours of those two vertices.

Should I write this up "properly"? It's already discussed elsewhere on the 'net.