Fetching the paper…

Reading the bibliography…

2022

Rainbow cycles in properly edge-colored graphs

Kim, Jaehoon, Lee, Joonkyung, Liu, Hong et al.

Original
PDF
Post on X

Understand

We prove that every properly edge-colored $n$-vertex graph with average degree at least $100(\log n)^2$ contains a rainbow cycle, improving upon $(\log n)^{2+o(1)}$ bound due to Tomon.

We also prove that every properly colored $n$-vertex graph with at least $10^5 k^2 n^{1+1/k}$ edges contains a rainbow $2k$-cycle, which improves the previous bound $2^{ck^2}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\H{o}s--Simonovits supersaturation theorem for even cycles, which may be of independent interest.

Rainbow cycles in properly edge-colored graphs · Around

Built on

Cycles of even length in graphs
J. A. Bondy and M. Simonovits · 1974
Earlier work this paper cites.
Cube-supersaturated graphs and related problems
P. Erdős and M. Simonovits · 1984
Earlier work this paper cites.

Similar

The size of bipartite graphs with a given girth
S. Hoory · 2002
Cited alongside, same era.
Rainbow Turán problems
P. Keevash, D. Mubayi, B. Sudakov, and J. Verstraëte · 2007
Cited alongside, same era.
Rainbow Turán number of even cycles, repeated patterns and blow-ups of cycles
O. Janzer
Cited in the paper.
On the Turán number of the hypercube
Original
O. Janzer and B. Sudakov
Cited in the paper.
Robust (rainbow) subdivisions and simplicial cycles
Original
I. Tomon
Cited in the paper.

Then

Turán numbers of subdivided graphs
T. Jiang and R. Seiver · 2012
Later among the works it cites.
Rainbow Turán problem for even cycles
S. Das, C. Lee, and B. Sudakov · 2013
Later among the works it cites.

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…