The Library
Non-bipartite k-common graphs
Tools
Králʼ, Daniel, Noel, Jonathan A., Norine, S., Volec, J. and Wei, F. (2022) Non-bipartite k-common graphs. Combinatorica, 42 . pp. 87-114. doi:10.1007/s00493-020-4499-9 ISSN 0209-9683.
|
PDF
WRAP-Non-bipartite-k-common-graphs-Kral-2020.pdf - Accepted Version - Requires a PDF viewer. Download (776Kb) | Preview |
Official URL: https://doi.org/10.1007/s00493-020-4499-9
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.
Item Type: | Journal Article | ||||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Subjects: | Q Science > QA Mathematics | ||||||||||||||||||
Divisions: | Faculty of Science, Engineering and Medicine > Science > Mathematics | ||||||||||||||||||
Library of Congress Subject Headings (LCSH): | Bipartite graphs, Graph coloring, Graph theory | ||||||||||||||||||
Journal or Publication Title: | Combinatorica | ||||||||||||||||||
Publisher: | Springer | ||||||||||||||||||
ISSN: | 0209-9683 | ||||||||||||||||||
Official Date: | February 2022 | ||||||||||||||||||
Dates: |
|
||||||||||||||||||
Volume: | 42 | ||||||||||||||||||
Page Range: | pp. 87-114 | ||||||||||||||||||
DOI: | 10.1007/s00493-020-4499-9 | ||||||||||||||||||
Status: | Peer Reviewed | ||||||||||||||||||
Publication Status: | Published | ||||||||||||||||||
Reuse Statement (publisher, data, author rights): | This version of the article has been accepted for publication, after peer review (when applicable) and is subject to Springer Nature’s AM terms of use, but is not the Version of Record and does not reflect post-acceptance improvements, or any corrections. The Version of Record is available online at: https://doi.org/10.1007/s00493-020-4499-9 | ||||||||||||||||||
Access rights to Published version: | Restricted or Subscription Access | ||||||||||||||||||
Date of first compliant deposit: | 15 October 2020 | ||||||||||||||||||
Date of first compliant Open Access: | 18 February 2023 | ||||||||||||||||||
RIOXX Funder/Project Grant: |
|
||||||||||||||||||
Related URLs: | |||||||||||||||||||
Open Access Version: |
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |
Downloads
Downloads per month over past year