The minimum number of cycles of length 0 modulo k in graphs with no proper k-coloring
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
- Three-ends Furstenberg estimates and approximate rectangles
- Multicolor Ramsey numbers of ordered matchings
- Exponential random graph models with soft clique constraints
- A Full-Sequence Quantitative Gap Between the Chromatic and Cochromatic Numbers of a Random Graph
- Ehrhart positivity for paving positroids
- Nonlinear lower-tail large deviations at criticality