WorksMathematics
The minimum number of cycles of length modulo in graphs with no proper -coloring
Abstract
Consider an integer . Toft and Tuza observed that every graph with no proper -coloring has a cycle of length modulo . Brewster, McGuinness, Moore, and Noel conjectured the following quantitative strengthening: every graph with no proper -coloring has at least cycles whose lengths are divisible by . The conjecture is sharp, as demonstrated by the complete graph on vertices. Kim and Picollelli confirmed the conjecture for . We establish the conjecture for every . In other words, we determine the minimum number of cycles of length modulo in a graph with no proper -coloring.
Introduction
All graphs considered in this paper are finite and simple, which means no loops and no parallel edges. Let denote the complete graph on vertices, and an -cycle is a cycle of length . Given a graph , a proper -coloring of is a function such that for every edge . The minimum for which has a proper -coloring is the chromatic number of , denoted .
A trivial observation is that every graph with no proper 2-coloring has an odd cycle, which is a cycle of length 1 modulo 2. Tuza [13] extended this to every integer : every graph with no proper -coloring has a cycle of length 1 modulo . In [13], it is also stated that Toft and Tuza observed that for , every graph with no proper -coloring has a cycle of length 0 modulo . Note that the bound on is sharp as an odd cycle has neither a proper 2-coloring nor a cycle of length 0 modulo 2. More generally, Chen, Ma, and Zang [3] proved a result implying that for and , every graph with no proper -coloring has a cycle of length modulo . The exception of is necessary as has neither a proper -coloring nor a cycle of length 2 modulo . For , Diwan, Kenkre, and Vishwanathan [6] showed that every graph with no proper -coloring has a cycle of length 2 modulo . Resolving a conjecture by Sudakov and Verstraëte [12], Gao, Huo, Liu, and Ma [7] proved that every graph with no proper -coloring has cycles of consecutive lengths. See also [8].
A graph with no proper -coloring has a subgraph with minimum degree at least , otherwise, the graph is -degenerate and thus has a proper -coloring. Dean [4] conjectured that for , every graph with minimum degree at least has a cycle of length 0 modulo . This conjecture was proved for by Chen and Saito [2] and for by Dean, Lesniak, and Saito [5]. Recently, Luo, Ma, and Zhao [10] proved Dean’s conjecture for every , leaving only the case open.
Once existence is guaranteed, a natural followup question is a quantitative question: given a graph with no proper -coloring, what is the guaranteed number of cycles of length 0 modulo ? For , the complete graph has no proper -coloring and has cycles of length 0 modulo . Note that the only possible cycles of length 0 modulo in are -cycles. Brewster, McGuinness, Moore, and Noel [1] conjectured that among all graphs with no proper -coloring, minimizes the number of cycles of length 0 modulo .
Conjecture 1 (Brewster, McGuinness, Moore, and Noel [1]). For every , every graph with no proper -coloring has at least cycles of length 0 modulo .
Brewster, McGuinness, Moore, and Noel [1] proved the following factorial lower bound, which is smaller than the conjectured bound by a factor of .
Theorem 2 (Brewster, McGuinness, Moore, and Noel [1]). For every , every graph with no proper -coloring has at least cycles of length 0 modulo .
Strengthening results in [13], Moore and West [11] proved further counting results regarding the number of cycles of certain lengths modulo through a given edge. They also proved that for , every graph with no proper -coloring has cycles of length 1 modulo . Note that this bound is sharp as again demonstrated by . For the number of cycles of length 0 modulo in a graph with no proper -coloring, their results guarantee cycles, recovering the result in Theorem 2.
Kim and Picollelli [9] confirmed Conjecture 1 for . We establish Conjecture 1 for every .
Theorem 3. For every , every graph with no proper -coloring has at least cycles of length 0 modulo .
Recall that the bound of is tight by .
Our proof uses the approach of Brewster, McGuinness, Moore, and Noel [1]. Relative to a vertex ordering, an -cycle is good if it can be traversed with at most backward edges, where an edge is backward when traversed from a later vertex to an earlier vertex in the vertex ordering. In § 2, we show that if has no proper -coloring but has a proper -coloring, then every ordering induced by a proper -coloring of , with placed last, has at least good cycles. In § 3, we show that a fixed cycle is good for at most permutations of the colors of a fixed proper -coloring. Finally, we prove Theorem 3 by combining these bounds in § 4. We also suggest some future directions.
Counting good cycles
In this section, we show that certain vertex orderings of a graph with chromatic number at least yield at least good cycles. We begin with a recoloring lemma.
Fix . Let be a graph. Given a labeling , an edge is -monochromatic if . Let be the digraph on where is an arc if and only if and . Thus a directed path of length increases the label by , modulo . Clearly, has no loops and no directed 2-cycles.
The following lemma is a version of the recoloring argument used by Moore and West [11]; see also Kim and Picollelli [9].
Lemma 4. For , let be a graph with , and let be a labeling of . For each -monochromatic edge , let the two endpoints be and . Then there exist -monochromatic edges such that can reach in .
Proof. Let be the set of -monochromatic edges of . Since has no proper -coloring, is nonempty; otherwise, replacing each label with modulo is a proper -coloring of , a contradiction. Let be the set of vertices reachable in from for some . Note that for every .
Suppose to the contrary that for every . Define a labeling where
Every edge is properly colored by , since and . Assume is monochromatic by . Thus and without loss of generality let and . Since , we know . Thus, is an arc of . Since , this implies , a contradiction. Thus is a proper -coloring of , a contradiction.
Let denote the graph with an ordering on its vertices. A traversal of an edge from to is forward if and backward otherwise. For a cycle in , let denote with one of the two cyclic traversals fixed. We call good if has length and has at most backward edges. We also call good if one of its two cyclic traversals is good. Note that the two cyclic traversals cannot be both good. One has backward edges and the other has backward edges. If both were good, then , which contradicts .
Lemma 5. For , let be a graph with . Suppose has a vertex such that has a proper -coloring . Let be a vertex ordering of obtained by ordering the vertices of in nondecreasing order of their colors under , and placing last. Then has at least distinct good cycles.
Proof. Extend to by setting . Let . Since has no proper -coloring, is nonempty. The only -monochromatic edges of are for . Let .
We prove the lemma in four steps. First, we define new labelings obtained by modifying . Second, to the endpoints of each -monochromatic edge, we assign and . Third, using Lemma 4, we find a good cycle for each containing a specific vertex . Finally, we show that these good cycles are pairwise distinct by these 's.
Step 1. New labelings .
For a vertex , let denote the length of a shortest directed path from to in , and let if is not reachable from . Note that each arc increases the label by , modulo . For , every finite is a positive multiple of since . In particular, .
For , let . Note that and . Let be the set of vertices that can reach some vertex of in . We remark that paths of length are allowed. Since , we know . Each vertex satisfies and has a directed path to entirely inside . For , we have if and only if . Since , we have , in particular, for .
For , define a new labeling by decreasing the label of each vertex in by exactly . Note that vertices in receive a label of under . Let .
Step 2. Assigning and to endpoints of -monochromatic edges.
For each -monochromatic edge of , we assign and to its endpoints as follows.
First, let be a newly -monochromatic edge. Up to renaming and if necessary, is an arc of where , , and . Let .
We claim and . Indeed, let be a directed path from to entirely in , which exists since . If , then followed by shows that , a contradiction, so . Since , we know , so and . Moreover, followed by is a directed path from to in , so .
Now, consider an originally -monochromatic edge of , so . If , then , so is an arc of . Otherwise, , so remains -monochromatic and . Let and . Since is a positive multiple of , we know and , so .
Consequently, every -monochromatic edge has
and either or and .
Step 3. Good cycles for .
We first show that every directed cycle in is good for . Note that .
Let be an edge of with . If is not -monochromatic, then . Since the label of an endpoint may change by exactly under , we know . Otherwise, is -monochromatic, so , , and . Since , we know . Hence, for every edge with . Since every arc of satisfies , we know if and if .
Now let be a directed -cycle in with backward edges. Since , we know , so is good.
We next show that contains a directed cycle through some vertex of . Recall the assignment of and for each -monochromatic edges from Step 2. By Lemma 4, there are -monochromatic edges such that can reach in . Let . We claim that can reach in through . We first show can reach . By (1), either and or . If , then there is nothing to show. Otherwise, , so there is a directed path in from to some entirely inside . Since the labels of vertices on this path decrease by exactly 1 under , the path remains directed in . Moreover, and , so . Thus is an arc of , so can reach .
By (1), , there is a shortest directed path from to in . Every vertex on satisfies , so no vertex on is in . Therefore, the labels of vertices on are unchanged under , so remains a directed path in .
Combining these paths gives a closed directed walk from to to back to in . This walk is nonempty since . Indeed, implies and if , then so .
A shortest nonempty closed directed walk in starting and ending at is a directed cycle through . Let be its underlying cycle. As shown above, is good, and .
Step 4. Counting distinct good cycles.
Suppose for some . Since a good cycle has only one good cyclic traversal, and are traversed in the same direction in and . Thus, for and for each edge on traversed from to , if and if . Thus , which implies that is constant on the vertices of .
On the other hand, since , we have . For each vertex on , we have and . Also, when or .
Therefore, Since , . However, by (1), , so . Since are on , this contradicts that is constant on vertices of .
Therefore are pairwise distinct.
Counting vertex orderings
In this section, we bound the number of vertex orderings for which a given cycle is good.
Lemma 6. For , let be a graph with a vertex where is a proper -coloring. For each permutation of the colors, let be the vertex ordering of obtained by ordering the vertices of in nondecreasing order of their colors under according to , and placing last. Then, each -cycle in is good in for at most permutations .
Proof. Fix a -cycle , and fix a cyclic traversal . We show that at most permutations make good.
We first observe that any consecutive edges of not involving must contain a backward edge. Otherwise, the colors of the vertices on the edges would be strictly increasing in the order specified by , which contradicts that there are colors. Case 1. avoids .
Partition the edges of into parts, where each part has consecutive edges on . By , each part contains a backward edge, so there are at least backward edges. If is good, then there must be exactly backward edges. This further implies that there are exactly forward edges between two closest backward edges.
Consequently, the vertices following each backward edge have all colors, appearing in the order specified by . In particular, the same ordering of all colors appears times around .
To determine a permutation for which is good, we only need to choose which of the colors comes first. The order of the remaining colors is then uniquely determined by their circular order along . Thus there are at most permutations for which is good.
Case 2. contains .
Let . Since is last in , the edge is backward, while the edge is forward. If is good, then at most edges in are backward.
Consider the last edges of the path . Partition these edges into parts where each part has consecutive edges. By , each of the parts contains at least one backward edge. It follows that are forward edges, so are distinct and appear in increasing order according to .
These colors determine their relative order in . There are exactly possible positions to insert the unique missing color in . Thus at most permutations make good.
Since has two possible cyclic traversals, and is good for at most permutations, we conclude is good for at most permutations.
The conclusion
We now prove Theorem 3. Given an integer , let be a graph with . Since , let be an induced subgraph of with the minimum number of vertices where and every vertex-minimal subgraph of satisfies . Fix . By minimality, has a proper -coloring . Consider all permutations of the colors and their induced vertex orderings . For each , relabel the colors so that their increasing order agrees with .
By Lemma 5, each has at least good cycles. Since each cycle is good for at most permutations by Lemma 6, contains at least cycles whose lengths are divisible by . Since every cycle of is also a cycle of , the desired lower bound follows.
To see that the bound is sharp, consider . Note that . There are ways to choose the vertices of a -cycle. For every choice of vertices, there are distinct -cycles. Thus has exactly cycles of length divisible by .
Further questions
Our result determines the minimum number of cycles of length modulo among graphs with no proper -coloring. More generally, Brewster, McGuinness, Moore, and Noel [1] explicitly suggested studying the same question for cycles of length modulo . (See also the discussion in the last section of [13]. Let denote the number of cycles of with length modulo . We have shown that every graph with no proper -coloring satisfies . As mentioned in the introduction, Moore and West [11] proved the analogous inequality for . For , the inequality holds since . Thus, it is natural to ask if this phenomenon continues:
Question 7. Let and . Does every graph with no proper -coloring satisfy ?
Another question is to characterize equality in Theorem 3. It is natural to restrict attention to critical graphs. Recall that a graph is -critical if and every proper subgraph of has a proper -coloring. Kim and Picollelli [9] showed that is the only 4-critical graph with exactly four cycles of length 0 modulo 3. We ask whether this extends to larger values of .
Question 8. Let . Is the unique -critical graph with exactly cycles of length 0 modulo ?
Declaration of LLM use
The authors used OpenAI’s models to assist with mathematical exploration and argument refinement. The authors developed and verified the mathematical arguments, revised the exposition, and take full responsibility for the contents of the article.
References
- [1]Richard C. Brewster, Sean McGuinness, Benjamin Moore, and Jonathan A. Noel. A dichotomy theorem for circular colouring reconfiguration. Theoret. Comput. Sci., 639:1–13, 2016.arxiv.org/abs/1508.05573
- [2]Guantao Chen and Akira Saito. Graphs with a cycle of length divisible by three. J. Combin. Theory Ser. B, 60(2):277–292, 1994.DOI
- [3]Zhibin Chen, Jie Ma, and Wenan Zang. Coloring digraphs with forbidden cycles. J. Combin. Theory Ser. B, 115:210–223, 2015.arxiv.org/abs/1403.8127
- [4]Nathaniel Dean. Which graphs are pancyclic modulo k? In Graph theory, combinatorics, and applications, Vol. 1 (Kalamazoo, MI, 1988), Wiley-Intersci. Publ., pages 315–325. Wiley, New York, 1991.
- [5]Nathaniel Dean, Linda Lesniak, and Akira Saito. Cycles of length 0 modulo 4 in graphs. Discrete Math., 121(1-3):37–49, 1993. Graph theory (Niedzica Castle, 1990).DOI
- [6]Ajit A. Diwan, Sreyash Kenkre, and Sundar Vishwanathan. Circumference, chromatic number and online coloring. Combinatorica, 33(3):319–334, 2013.arxiv.org/abs/0809.1710
- [7]Jun Gao, Qingyi Huo, Chun-Hung Liu, and Jie Ma. A unified proof of conjectures on cycle lengths in graphs. Int. Math. Res. Not. IMRN, (10):7615–7653, 2022.
- [8]Jun Gao, Qingyi Huo, and Jie Ma. A strengthening on odd cycles in graphs of given chromatic number. SIAM J. Discrete Math., 35(4):2317–2327, 2021.arxiv.org/abs/2012.10624
- [9]Sean Kim and Michael E. Picollelli. 4-chromatic graphs have at least four cycles of length 0 mod 3. Electron. J. Combin., 31(2):Paper No. 2.58, 12, 2024.
- [10]Yufan Luo, Jie Ma, and Ziyuan Zhao. Dean’s conjecture and cycles modulo k. arXiv:2601.13552, 2026.arxiv.org/abs/2601.13552
- [11]Benjamin R. Moore and Douglas B. West. Cycles in color-critical graphs. Electron. J. Combin., 28(4):Paper No. 4.35, 10, 2021.arxiv.org/abs/1912.03754
- [12]Benny Sudakov and Jacques Verstraëte. The extremal function for cycles of length ℓ mod k. Electron. J. Combin., 24(1):Paper No. 1.7, 8, 2017.arxiv.org/abs/1606.08532
- [13]Zsolt Tuza. Graph coloring in linear time. J. Combin. Theory Ser. B, 55(2):236–243, 1992.DOI