  Let $n_g(k)$ denote the smallest order of a $k$-chromatic graph of girth at
least $g$. We consider the problem of determining $n_g(k)$ for small values of
$k$ and $g$. After giving an overview of what is known about $n_g(k)$, we
provide some new lower bounds based on exhaustive searches, and then obtain
several new upper bounds using computer algorithms for the construction of
witnesses, and for the verification of their correctness. We also present the
first examples of reasonably small order for $k = 4$ and $g > 5$. In
particular, the new bounds include: $n_4(7) \leq 77$, $26 \leq n_6(4) \leq 66$,
$30 \leq n_7(4) \leq 171$.
