Abstract
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 [20]. 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.
Original language | English (US) |
---|---|
Pages (from-to) | 87-114 |
Number of pages | 28 |
Journal | Combinatorica |
Volume | 42 |
Issue number | 1 |
DOIs | |
State | Published - Feb 2022 |
All Science Journal Classification (ASJC) codes
- Discrete Mathematics and Combinatorics
- Computational Mathematics