  A graph H is k-common if the number of monochromatic copies of H in a
k-edge-coloring of K_n is asymptotically minimized by a random coloring. For
every k, we construct a connected non-bipartite k-common graph. This resolves a
problem raised by Jagger, Stovicek and Thomason [Combinatorica 16 (1996),
123-141]. We also show that a graph H is k-common for every k if and only if H
is Sidorenko and that H is locally k-common for every k if and only if H is
locally Sidorenko.
