On graphs without cycles of length 0 modulo 4

Ervin Győri; Binlong Li; Nika Salia; Casey Tompkins; Kitti Varga; Manran Zhu

doi:10.1016/j.jctb.2025.07.008

On graphs without cycles of length 0 modulo 4

Ervin Győri
, Binlong Li
, Nika Salia
, Casey Tompkins
, Kitti Varga
, Manran Zhu

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

Abstract

Bollobás proved that for every k and ℓ such that kZ+ℓ contains an even number, an n-vertex graph containing no cycle of length ℓmodk can contain at most a linear number of edges. The precise (or asymptotic) value of the maximum number of edges in such a graph is known for very few pairs ℓ and k. In this work we precisely determine the maximum number of edges in a graph containing no cycle of length 0mod4.

Original language	English
Pages (from-to)	7-29
Number of pages	23
Journal	Journal of Combinatorial Theory. Series B
Volume	176
DOIs	https://doi.org/10.1016/j.jctb.2025.07.008
State	Published - Jan 2026
Externally published	Yes

Bibliographical note

Publisher Copyright:
© 2025 Elsevier Inc.

Keywords

0 mod 4 cycles
Extremal Graph Theory
Forbidden cycles

ASJC Scopus subject areas

Theoretical Computer Science
Discrete Mathematics and Combinatorics
Computational Theory and Mathematics

Access to Document

10.1016/j.jctb.2025.07.008

Cite this

@article{ff09869062bb44c8a058a25d1ce3d6bf,

title = "On graphs without cycles of length 0 modulo 4",

abstract = "Bollob{\'a}s proved that for every k and ℓ such that kZ+ℓ contains an even number, an n-vertex graph containing no cycle of length ℓmodk can contain at most a linear number of edges. The precise (or asymptotic) value of the maximum number of edges in such a graph is known for very few pairs ℓ and k. In this work we precisely determine the maximum number of edges in a graph containing no cycle of length 0mod4.",

keywords = "0 mod 4 cycles, Extremal Graph Theory, Forbidden cycles",

author = "Ervin Gy{\H o}ri and Binlong Li and Nika Salia and Casey Tompkins and Kitti Varga and Manran Zhu",

note = "Publisher Copyright: {\textcopyright} 2025 Elsevier Inc.",

year = "2026",

month = jan,

doi = "10.1016/j.jctb.2025.07.008",

language = "English",

volume = "176",

pages = "7--29",

journal = "Journal of Combinatorial Theory. Series B",

issn = "0095-8956",

publisher = "Academic Press Inc.",

}

TY - JOUR

T1 - On graphs without cycles of length 0 modulo 4

AU - Győri, Ervin

AU - Li, Binlong

AU - Salia, Nika

AU - Tompkins, Casey

AU - Varga, Kitti

AU - Zhu, Manran

PY - 2026/1

Y1 - 2026/1

N2 - Bollobás proved that for every k and ℓ such that kZ+ℓ contains an even number, an n-vertex graph containing no cycle of length ℓmodk can contain at most a linear number of edges. The precise (or asymptotic) value of the maximum number of edges in such a graph is known for very few pairs ℓ and k. In this work we precisely determine the maximum number of edges in a graph containing no cycle of length 0mod4.

AB - Bollobás proved that for every k and ℓ such that kZ+ℓ contains an even number, an n-vertex graph containing no cycle of length ℓmodk can contain at most a linear number of edges. The precise (or asymptotic) value of the maximum number of edges in such a graph is known for very few pairs ℓ and k. In this work we precisely determine the maximum number of edges in a graph containing no cycle of length 0mod4.

KW - 0 mod 4 cycles

KW - Extremal Graph Theory

KW - Forbidden cycles

UR - https://www.scopus.com/pages/publications/105013552894

U2 - 10.1016/j.jctb.2025.07.008

DO - 10.1016/j.jctb.2025.07.008

M3 - Article

AN - SCOPUS:105013552894

SN - 0095-8956

VL - 176

SP - 7

EP - 29

JO - Journal of Combinatorial Theory. Series B

JF - Journal of Combinatorial Theory. Series B

ER -

On graphs without cycles of length 0 modulo 4

Abstract

Bibliographical note

Keywords

ASJC Scopus subject areas

Access to Document

Fingerprint

Cite this