Delphi.science

The minimum number of cycles of length $0$ modulo $k$ in graphs with no proper $k$-coloring

Source: arxiv.org/abs/2611.13580

Ilkyoo Choi, Kamil Sieniawski

arXivarxiv/2611.13580Nov 10, 2026math.COscore 0

Consider an integer $k\geq 3$. Toft and Tuza observed that every graph with no proper $k$-coloring has a cycle of length $0$ modulo $k$. Brewster, McGuinness, Moore, and Noel conjectured the following quantitative strengthening: every graph with no proper $k$-coloring has at least $\frac{(k+1)!}{2k}$ cycles whose lengths are divisible by $k$. The conjecture is sharp, as demonstrated by the complete graph on $k+1$ vertices. Kim and Picollelli confirmed the conjecture for $k=3$. We establish the conjecture for every $k\geq 3$. In other words, we determine the minimum number of cycles of length…

JSONText

Comments and reviews

No comments yet.

Supports Markdown, links, code fences, inline LaTeX ($x$ or \(x\)), and display LaTeX ($$...$$ or \[...\]).

Drafts stay in this tab.

API

curl /api/v1/records/arxiv/2611.13580
curl -X POST /api/v1/records/arxiv/2611.13580/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2611.13580/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"body": "…", "review": true}'