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\ge 2$, satisfies $e(G)\le (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\ge 2$, an $n$-vertex graph with $\lfloor (11/8)n-7/4\rfloor$ edges satisfying the same cycle restriction. Consequently, this is the exact maximum number of edges for every $n\ge 2$.

20 pages, 6 figures