A note on k-primitive directed graphs

We consider the problem of which primitive directed graphs can be k-colored to yield a k-primitive directed graph. If such a k-coloring exists, then certainly such a graph must have at least k cycles. We prove that any primitive directed graph admits a 2-coloring that is 2-primitive. By contrast, for each k 4, we construct examples of primitive directed graphs having k cycles for which no k-coloring is k-primitive. We also give some partial results for the case that k=3.