Rainbow Cycles in Properly Edge-Colored Graphs

Jaehoon Kim; Joonkyung Lee; Hong Liu; Tuan Tran

doi:10.1007/s00493-024-00101-7

Rainbow Cycles in Properly Edge-Colored Graphs

Jaehoon Kim, Joonkyung Lee, Hong Liu, Tuan Tran

Department of Mathematics

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

2 Citations (Scopus)

Abstract

We prove that every properly edge-colored n-vertex graph with average degree at least 32(log5n)² contains a rainbow cycle, improving upon the (logn)^2+o(1) bound due to Tomon. We also prove that every properly edge-colored n-vertex graph with at least 10⁵k³n^1+1/k edges contains a rainbow 2k-cycle, which improves the previous bound 2^{^ck²}n^1+1/k obtained by Janzer. Our method using homomorphism inequalities and a lopsided regularization lemma also provides a simple way to prove the Erdős–Simonovits supersaturation theorem for even cycles, which may be of independent interest.

Original language	English
Pages (from-to)	909-919
Number of pages	11
Journal	Combinatorica
Volume	44
Issue number	4
DOIs	https://doi.org/10.1007/s00493-024-00101-7
Publication status	Published - 2024 Aug

Bibliographical note

Publisher Copyright:
© The Author(s) 2024.

All Science Journal Classification (ASJC) codes

Discrete Mathematics and Combinatorics
Computational Mathematics

Access to Document

10.1007/s00493-024-00101-7

Cite this

@article{39869b1ac1af4f7ea6bc3e88d724f7d9,

title = "Rainbow Cycles in Properly Edge-Colored Graphs",

abstract = "We prove that every properly edge-colored n-vertex graph with average degree at least 32(log5n)2 contains a rainbow cycle, improving upon the (logn)2+o(1) bound due to Tomon. We also prove that every properly edge-colored n-vertex graph with at least 105k3n1+1/k edges contains a rainbow 2k-cycle, which improves the previous bound 2ck2n1+1/k obtained by Janzer. Our method using homomorphism inequalities and a lopsided regularization lemma also provides a simple way to prove the Erd{\H o}s–Simonovits supersaturation theorem for even cycles, which may be of independent interest.",

keywords = "Extremal number, Rainbow cycles, Turan problem",

author = "Jaehoon Kim and Joonkyung Lee and Hong Liu and Tuan Tran",

note = "Publisher Copyright: {\textcopyright} The Author(s) 2024.",

year = "2024",

month = aug,

doi = "10.1007/s00493-024-00101-7",

language = "English",

volume = "44",

pages = "909--919",

journal = "Combinatorica",

issn = "0209-9683",

publisher = "Janos Bolyai Mathematical Society",

number = "4",

}

TY - JOUR

T1 - Rainbow Cycles in Properly Edge-Colored Graphs

AU - Kim, Jaehoon

AU - Lee, Joonkyung

AU - Liu, Hong

AU - Tran, Tuan

N1 - Publisher Copyright: © The Author(s) 2024.

PY - 2024/8

Y1 - 2024/8

N2 - We prove that every properly edge-colored n-vertex graph with average degree at least 32(log5n)2 contains a rainbow cycle, improving upon the (logn)2+o(1) bound due to Tomon. We also prove that every properly edge-colored n-vertex graph with at least 105k3n1+1/k edges contains a rainbow 2k-cycle, which improves the previous bound 2ck2n1+1/k obtained by Janzer. Our method using homomorphism inequalities and a lopsided regularization lemma also provides a simple way to prove the Erdős–Simonovits supersaturation theorem for even cycles, which may be of independent interest.

AB - We prove that every properly edge-colored n-vertex graph with average degree at least 32(log5n)2 contains a rainbow cycle, improving upon the (logn)2+o(1) bound due to Tomon. We also prove that every properly edge-colored n-vertex graph with at least 105k3n1+1/k edges contains a rainbow 2k-cycle, which improves the previous bound 2ck2n1+1/k obtained by Janzer. Our method using homomorphism inequalities and a lopsided regularization lemma also provides a simple way to prove the Erdős–Simonovits supersaturation theorem for even cycles, which may be of independent interest.

KW - Extremal number

KW - Rainbow cycles

KW - Turan problem

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

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

U2 - 10.1007/s00493-024-00101-7

DO - 10.1007/s00493-024-00101-7

M3 - Article

AN - SCOPUS:85191968168

SN - 0209-9683

VL - 44

SP - 909

EP - 919

JO - Combinatorica

JF - Combinatorica

IS - 4

ER -

Rainbow Cycles in Properly Edge-Colored Graphs

Abstract

Bibliographical note

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this