Non-Bipartite K-Common Graphs

Daniel Král’, Jonathan A. Noel, Sergey Norin, Jan Volec, Fan Wei

Research output: Contribution to journalArticlepeer-review

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 languageEnglish (US)
Pages (from-to)87-114
Number of pages28
JournalCombinatorica
Volume42
Issue number1
DOIs
StatePublished - Feb 2022

All Science Journal Classification (ASJC) codes

  • Discrete Mathematics and Combinatorics
  • Computational Mathematics

Fingerprint

Dive into the research topics of 'Non-Bipartite K-Common Graphs'. Together they form a unique fingerprint.

Cite this