@article{038e097044f449c1b25397db97630b4b,

title = "Non-Bipartite K-Common Graphs",

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, {\v S}tov{\'i}{\v c}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.",

author = "Daniel Kr{\'a}l{\textquoteright} and Noel, {Jonathan A.} and Sergey Norin and Jan Volec and Fan Wei",

note = "Funding Information: The work of the first, second and fourth authors has received funding from the European Research Council (ERC) under the European Union{\textquoteright}s Horizon 2020 research and innovation programme (grant agreement No 648509). This publication reflects only its authors{\textquoteright} view; the European Research Council Executive Agency is not responsible for any use that may be made of the information it contains. The first and the fourth author were also supported by the MUNI Award in Science and Humanities of the Grant Agency of Masaryk University. The second author was also supported by the Leverhulme Trust Early Career Fellowship ECF-2018-534. The third author was supported by an NSERC Discovery grant. The fifth author was supported by IAS Founders{\textquoteright} Circle funding provided by Cynthia and Robert Hillas. Acknowledgement Publisher Copyright: {\textcopyright} 2022, J{\'a}nos Bolyai Mathematical Society and Springer-Verlag Berlin Heidelberg.",

year = "2022",

month = feb,

doi = "10.1007/s00493-020-4499-9",

language = "English (US)",

volume = "42",

pages = "87--114",

journal = "Combinatorica",

issn = "0209-9683",

publisher = "Janos Bolyai Mathematical Society",

number = "1",

}