  The graph complexity of a compact 3-manifold is defined as the minimum order
among all 4-colored graphs representing it. Exact calculations of graph
complexity have been already performed, through tabulations, for closed
orientable manifolds (up to graph complexity 32) and for compact orientable
3-manifolds with toric boundary (up to graph complexity 12) and for infinite
families of lens spaces. In this paper we extend to graph complexity 14 the
computations for orientable manifolds with toric boundary and we give two-sided
bounds for the graph complexity of tetrahedral manifolds. As a consequence, we
compute the exact value of this invariant for an infinite family of such
manifolds.
