Channel Assignment is a problem of assigning frequencies (integer numbers) to radio emitters (vertices of a graph) such that the emitters are not interfering each other (weight on edges represent minimum allowed frequency differences) and the span of assigned frequencies is minimum.

Subgraph Isomorphism is a well known problem of checking if one graph is isomorphic with a subgraph of another.

Both of them have brute force O*(n!) algorithms. In both cases this is optimal. It turns out that the proofs of the lower bounds of these quite unrelated problems can share some techniques.