The maximum number of copies of an even cycle in a planar graph

EUROCOMB’23

Abstract
We resolve a conjecture of Cox and Martin by determining asymptotically for every $k\ge 2$ the maximum number of copies of $C_{2k}$ in an $n$-vertex planar graph.

Pages:
526–531
References

Noga Alon and Yair Caro. On the number of subgraphs of prescribed type of pla- nar graphs with a given number of vertices. In North-Holland Mathematics Studies, volume 87, pages 25-36. Elsevier, 1984.
https://doi.org/10.1016/S0304-0208(08)72803-2

Asaf Cohen Antonir and Asaf Shapira. Bounding the number of odd paths in planar graphs via convex optimization. arXiv preprint arXiv:2208.02097, 2022.

Christopher Cox and Ryan R Martin. Counting paths, cycles, and blow-ups in planar graphs. Journal of Graph Theory, 101(3):521-558, 2022.
https://doi.org/10.1002/jgt.22838

Christopher Cox and Ryan R Martin. The maximum number of 10-and 12-cycles in a planar graph. Discrete Mathematics, 346(2):113245, 2023.
https://doi.org/10.1016/j.disc.2022.113245

David Eppstein. Connectivity, graph minors, and subgraph multiplicity. Journal of Graph Theory, 17(3):409-416, 1993.
https://doi.org/10.1002/jgt.3190170314

Ervin Győri, Addisu Paulos, Nika Salia, Casey Tompkins, and Oscar Zamora. The maximum number of pentagons in a planar graph. arXiv preprint arXiv:1909.13532, 2019.

Ervin Győri, Addisu Paulos, Nika Salia, Casey Tompkins, and Oscar Zamora. Generalized planar tur'an numbers. arXiv preprint arXiv:2002.04579, 2020.
https://doi.org/10.37236/9603

Seifollah Louis Hakimi and Edward F Schmeichel. On the number of cycles of length k in a maximal planar graph. Journal of Graph Theory, 3(1):69-86, 1979.
https://doi.org/10.1002/jgt.3190030108

Tony Huynh, Gwenaël Joret, and David R Wood. Subgraph densities in a surface. Combinatorics, Probability and Computing, 31(5):812-839, 2022.
https://doi.org/10.1017/S0963548321000560

Casimir Kuratowski. Sur le probleme des courbes gauches en topologie. Fundamenta mathematicae, 15(1):271-283, 1930.
https://doi.org/10.4064/fm-15-1-271-283

Nicholas C Wormald. On the frequency of 3-connected subgraphs of planar graphs. Bulletin of the Australian Mathematical Society, 34(2):309-317, 1986.
https://doi.org/10.1017/S0004972700010182

Metrics

0

Views

0

PDF views