Every 2-connected n-vertex graph with more than floor((3n-1)/2) edges contains a cycle whose length is a multiple of 4, and this bound is sharp for all n at least 12.
On graphs without cycles of length 0 modulo 4
1 Pith paper cite this work. Polarity classification is still indexing.
1
Pith paper citing it
abstract
Bollob\'as proved that for every $k$ and $\ell$ such that $k\mathbb{Z}+\ell$ contains an even number, an $n$-vertex graph containing no cycle of length $\ell \bmod k$ 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 $\ell$ and $k$. In this work we precisely determine the maximum number of edges in a graph containing no cycle of length $0 \bmod 4$.
citation-role summary
background 1
citation-polarity summary
fields
math.CO 1years
2025 1verdicts
CONDITIONAL 1roles
background 1polarities
unclear 1representative citing papers
citing papers explorer
-
On $2$-connected graphs avoiding cycles of length $0$ modulo $4$
Every 2-connected n-vertex graph with more than floor((3n-1)/2) edges contains a cycle whose length is a multiple of 4, and this bound is sharp for all n at least 12.