PreprintarXiv licencearXiv
On graphs without cycles of length $0$ modulo $3$ or $4$ modulo $6$
Abstract
We study graphs containing no cycle whose length is divisible by $3$ or congruent to $4$ modulo $6$. We prove that every such n-vertex graph G, where n ≥ 2, satisfies e(G) ≤ (11/8)n−7/4. Moreover, equality holds if and only if n=8k+2 for some nonnegative integer k and G is isomorphic to the explicitly constructed graph Hk. We also construct, for every n≥2, an n-vertex graph with ⌊ (11/8)n−7/4 ⌋ edges satisfying the same cycle restriction. Consequently, this is the exact maximum number of edges for every n ≥ 2.
Related
- Extremal graphs without cycles of length 0 modulo 4
- Polynomial Length Cycles In Tough Graphs
- Counting hypergraphs without linear cycles of fixed length
- Total-coloring of planar graphs with maximum degree 6 and without prescribed 4-cycles
- Small graphs without power-of-two cycles: a lower bound of 24, a correction to a construction of Exoo, and explicit bounds for f(k)
BibTeX
@misc{ueoro2026graphs,
title = {{On graphs without cycles of length $0$ modulo $3$ or $4$ modulo $6$}},
author = {Takahiro Ueoro},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2608.06698},
eprint = {2608.06698},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2608.06698},
}
RIS
TY - UNPB
TI - On graphs without cycles of length $0$ modulo $3$ or $4$ modulo $6$
AU - Takahiro Ueoro
PY - 2026
DA - 2026/10/26
PB - arXiv
DO - 10.48550/arxiv.2608.06698
UR - https://arxiv.org/abs/2608.06698
AB - We study graphs containing no cycle whose length is divisible by $3$ or congruent to $4$ modulo $6$. We prove that every such n-vertex graph G, where n ≥ 2, satisfies e(G) ≤ (11/8)n−7/4. Moreover, equality holds if and only if n=8k+2 for some nonnegative integer k and G is isomorphic to the explicitly constructed graph H_k. We also construct, for every n≥2, an n-vertex graph with ⌊ (11/8)n−7/4 ⌋ edges satisfying the same cycle restriction. Consequently, this is the exact maximum number of edges for every n ≥ 2.
ER -