Non-Bipartite K-Common Graphs
Publication
, Journal Article
Král’, D; Noel, JA; Norin, S; Volec, J; Wei, F
Published in: Combinatorica
February 1, 2022
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.
Duke Scholars
Altmetric Attention Stats
Dimensions Citation Stats
Published In
Combinatorica
DOI
EISSN
1439-6912
ISSN
0209-9683
Publication Date
February 1, 2022
Volume
42
Issue
1
Start / End Page
87 / 114
Related Subject Headings
- Computation Theory & Mathematics
- 49 Mathematical sciences
- 46 Information and computing sciences
- 08 Information and Computing Sciences
- 01 Mathematical Sciences
Citation
APA
Chicago
ICMJE
MLA
NLM
Král’, D., Noel, J. A., Norin, S., Volec, J., & Wei, F. (2022). Non-Bipartite K-Common Graphs. Combinatorica, 42(1), 87–114. https://doi.org/10.1007/s00493-020-4499-9
Král’, D., J. A. Noel, S. Norin, J. Volec, and F. Wei. “Non-Bipartite K-Common Graphs.” Combinatorica 42, no. 1 (February 1, 2022): 87–114. https://doi.org/10.1007/s00493-020-4499-9.
Král’ D, Noel JA, Norin S, Volec J, Wei F. Non-Bipartite K-Common Graphs. Combinatorica. 2022 Feb 1;42(1):87–114.
Král’, D., et al. “Non-Bipartite K-Common Graphs.” Combinatorica, vol. 42, no. 1, Feb. 2022, pp. 87–114. Scopus, doi:10.1007/s00493-020-4499-9.
Král’ D, Noel JA, Norin S, Volec J, Wei F. Non-Bipartite K-Common Graphs. Combinatorica. 2022 Feb 1;42(1):87–114.
Published In
Combinatorica
DOI
EISSN
1439-6912
ISSN
0209-9683
Publication Date
February 1, 2022
Volume
42
Issue
1
Start / End Page
87 / 114
Related Subject Headings
- Computation Theory & Mathematics
- 49 Mathematical sciences
- 46 Information and computing sciences
- 08 Information and Computing Sciences
- 01 Mathematical Sciences