In computer science and graph theory, the term color-coding refers to an algorithmic technique which is useful in the discovery of network motifs. For example, it can be used to detect a simple path of length k in a given graph. The traditional color-coding algorithm is probabilistic, but it can be derandomized without much overhead in the running time.

Color-coding also applies to the detection of cycles of a given length, and more generally it applies to the subgraph isomorphism problem (an NP-complete problem), where it yields polynomial time algorithms when the subgraph pattern that it is trying to detect has bounded treewidth.

The color-coding method was proposed and analyzed in 1994 by Noga Alon, Raphael Yuster, and Uri Zwick.

The following results can be obtained through the method of color-coding:

To solve the problem of finding a subgraph ${\displaystyle H=(V_{H},E_{H})}$ in a given graph G = (V, E), where H can be a path, a cycle, or any bounded treewidth graph where ${\displaystyle |V_{H}|=O(\log |V|)}$, the method of color-coding begins by randomly coloring each vertex of G with ${\displaystyle k=|V_{H}|}$ colors, and then tries to find a colorful copy of H in colored G. Here, a graph is colorful if every vertex in it is colored with a distinct color. This method works by repeating (1) random coloring a graph and (2) finding colorful copy of the target subgraph, and eventually the target subgraph can be found if the process is repeated a sufficient number of times.

Suppose a copy of H in G becomes colorful with some non-zero probability p. It immediately follows that if the random coloring is repeated ⁠1/p⁠ times, then this copy is expected to become colorful once. Note that though p is small, it is shown that if ${\displaystyle |V_{H}|=O(\log |V|)}$, p is only polynomially small. Suppose again there exists an algorithm such that, given a graph G and a coloring which maps each vertex of G to one of the k colors, it finds a copy of colorful H, if one exists, within some runtime O(r). Then the expected time to find a copy of H in G, if one exists, is ${\displaystyle O({\tfrac {r}{p}})}$.

Sometimes it is also desirable to use a more restricted version of colorfulness. For example, in the context of finding cycles in planar graphs, it is possible to develop an algorithm that finds well-colored cycles. Here, a cycle is well-colored if its vertices are colored by consecutive colors.

An example would be finding a simple cycle of length k in graph G = (V, E).