A graph H is k-common if the number of monochromatic copies of H in a k-edge-coloring of Kn 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, Štovíček and Thomason . 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.
All Science Journal Classification (ASJC) codes
- Discrete Mathematics and Combinatorics
- Computational Mathematics