Color Coding

Color coding is a randomized algorithmic technique introduced by Alon et al. (1995) for finding and counting small subgraphs in a graph. It randomly colors the vertices of a graph and then searches for a copy of the desired subgraph whose vertices all receive distinct colors.

The method is especially useful for detecting simple paths and cycles of a specified length. A derandomized version can be obtained using families of perfect hash functions (Alon et al. 1995).