  Given a graph sequence $\{G_n\}_{n \geq 1}$ denote by $T_3(G_n)$ the number
of monochromatic triangles in a uniformly random coloring of the vertices of
$G_n$ with $c \geq 2$ colors. This arises as a generalization of the birthday
paradox, where $G_n$ corresponds to a friendship network and $T_3(G_n)$ counts
the number of triples of friends with matching birthdays. In this paper we
prove a central limit theorem (CLT) for $T_3(G_n)$ with explicit error rates.
The proof involves constructing a martingale difference sequence by carefully
ordering the vertices of $G_n$, based on a certain combinatorial score
function, and using a quantitive version of the martingale CLT. We then relate
this error term to the well-known fourth moment phenomenon, which,
interestingly, holds only when the number of colors $c \geq 5$. We also show
that the convergence of the fourth moment is necessary to obtain a Gaussian
limit for any $c \geq 2$, which, together with the above result, implies that
the fourth-moment condition characterizes the limiting normal distribution of
$T_3(G_n)$, whenever $c \geq 5$. Finally, to illustrate the promise of our
approach, we include an alternative proof of the CLT for the number of
monochromatic edges, which provides quantitative rates for the results obtained
in Bhattacharya et al. (2017).
