Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2605.02731 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866911644652666880 |
|---|---|
| author | Choi, Ilkyoo Chu, Hojin Kim, Ringi Park, Boram |
| author_facet | Choi, Ilkyoo Chu, Hojin Kim, Ringi Park, Boram |
| contents | Dean conjectured that for each integer $k \ge 3$, every graph with minimum degree at least $k$ has a cycle whose length is divisible by $k$; this conjecture is known to be true for all $k\neq 5$. For $k\in\{3,4\}$, stronger statements are true: every graph with minimum degree at least $2$ and at most $k-2$ vertices of degree $2$ has a cycle whose length is divisible by $k$.
We further strengthen these results by characterizing all graphs with minimum degree at least $2$ and at most three vertices of degree $2$ that have no cycle of length divisible by $k$, for each $k\in\{3,4\}$. As a corollary, we obtain that every graph with minimum degree at least $2$ and at most two vertices of degree $2$ has a cycle whose length is divisible by $3$, and that every graph on at least nine vertices with minimum degree at least $2$ and at most three vertices of degree $2$ has a cycle whose length is divisible by $4$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2605_02731 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Existence of cycles of length divisible by 3 or 4 Choi, Ilkyoo Chu, Hojin Kim, Ringi Park, Boram Combinatorics Dean conjectured that for each integer $k \ge 3$, every graph with minimum degree at least $k$ has a cycle whose length is divisible by $k$; this conjecture is known to be true for all $k\neq 5$. For $k\in\{3,4\}$, stronger statements are true: every graph with minimum degree at least $2$ and at most $k-2$ vertices of degree $2$ has a cycle whose length is divisible by $k$. We further strengthen these results by characterizing all graphs with minimum degree at least $2$ and at most three vertices of degree $2$ that have no cycle of length divisible by $k$, for each $k\in\{3,4\}$. As a corollary, we obtain that every graph with minimum degree at least $2$ and at most two vertices of degree $2$ has a cycle whose length is divisible by $3$, and that every graph on at least nine vertices with minimum degree at least $2$ and at most three vertices of degree $2$ has a cycle whose length is divisible by $4$. |
| title | Existence of cycles of length divisible by 3 or 4 |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2605.02731 |