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

arXiv:2611.13580 · math.CO · Submitted 2026-11-10 · Read on arXiv

math.CO

Submitted: 2026-11-10

Updated: 2026-11-10

License: http://creativecommons.org/licenses/by/4.0/

The gist: Consider an integer k at least 3.

Abstract

Consider an integer k at least 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(k+1)! over 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 at least 3. In other words, we determine the minimum number of cycles of length 0 modulo k in a graph with no proper k-coloring.

Sources

Related papers