Non-Bipartite K-Common Graphs

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

doi:10.1007/s00493-020-4499-9

Non-Bipartite K-Common Graphs

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

Mathematics

Research output: Contribution to journal › Article › peer-review

5 Scopus citations

Abstract

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, Š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	https://doi.org/10.1007/s00493-020-4499-9
State	Published - Feb 2022

All Science Journal Classification (ASJC) codes

Discrete Mathematics and Combinatorics
Computational Mathematics

Access to Document

10.1007/s00493-020-4499-9

Cite this

@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 = "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",

}

TY - JOUR

T1 - Non-Bipartite K-Common Graphs

AU - Král’, Daniel

AU - Noel, Jonathan A.

AU - Norin, Sergey

AU - Volec, Jan

AU - Wei, Fan

PY - 2022/2

Y1 - 2022/2

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=85124762881&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85124762881&partnerID=8YFLogxK

U2 - 10.1007/s00493-020-4499-9

DO - 10.1007/s00493-020-4499-9

M3 - Article

AN - SCOPUS:85124762881

SN - 0209-9683

VL - 42

SP - 87

EP - 114

JO - Combinatorica

JF - Combinatorica

IS - 1

ER -

Non-Bipartite K-Common Graphs

Abstract

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this