Minimum number of shopping trips for a group of people to buy presents for each other
I can see how to reduce this problem to Graph Colouring, which gives you a tool for solving the problem (for small instances!), but not yet how to reduce in the other direction (which would establish NP-hardness).

The basic idea is to build a graph that contains a vertex for every purchase, and an edge between any two purchases that cannot occur on the same trip; we then look to group the purchases into the smallest possible number of groups ("trips"), such that no two purchases in the same group would conflict.  Specifically, if $G = (V, E)$ is the original directed graph in which an edge $uv$ indicates that person $u$ needs to buy person $v$ a gift, then create an undirected graph $H = (X, Y)$ in which there is a vertex $x_{uv}$ for each edge $uv$ in $G$ and an (undirected) edge $x_{uv}x_{vw}$ whenever $uv$ and $vw$ are both (directed) edges in $G$ (if $v$ buys some $w$ a gift during a trip, then no one can buy $v$ a gift during that same trip).  A vertex colouring of $H$ is a partition of the necessary purchases (vertices in $H$) into trips (colours) that don't conflict (share an edge), and a vertex colouring of minimum size takes the fewest possible trips.

It might be possible to go in the other direction (reduce Graph Colouring, or some other NP-hard problem, to your problem, and thereby establish its NP-hardness), by adapting a reduction from 3SAT to Graph Colouring (as, e.g., detailed on p. 10 of Jeff Erickson's notes), but I haven't attempted this myself.