betaFeedback

WorksMathematics

The minimum number of cycles of length 00 modulo kk in graphs with no proper kk-coloring

Abstract

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

Introduction

All graphs considered in this paper are finite and simple, which means no loops and no parallel edges. Let KnK_n denote the complete graph on nn vertices, and an ℓ\ell-cycle is a cycle of length ℓ\ell. Given a graph GG, a proper kk-coloring of GG is a function φ:V(G)→{0,…,k−1}\varphi: V(G) \to\{0, \ldots, k - 1\} such that φ(x)≠φ(y)\varphi(x) \ne\varphi(y) for every edge xyxy. The minimum kk for which GG has a proper kk-coloring is the chromatic number of GG, denoted χ(G)\chi(G).

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 k≥3k \ge3: every graph with no proper kk-coloring has a cycle of length 1 modulo kk. In [13], it is also stated that Toft and Tuza observed that for k≥3k \ge3, every graph with no proper kk-coloring has a cycle of length 0 modulo kk. Note that the bound on kk 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 k≥3k \ge3 and r∈{0,…,k−1}∖{2}r \in\{0, \ldots, k - 1\} \setminus\{2\}, every graph with no proper kk-coloring has a cycle of length rr modulo kk. The exception of r=2r = 2 is necessary as Kk+1K_{k+1} has neither a proper kk-coloring nor a cycle of length 2 modulo kk. For r=2r = 2, Diwan, Kenkre, and Vishwanathan [6] showed that every graph with no proper (k+1)(k + 1)-coloring has a cycle of length 2 modulo kk. Resolving a conjecture by Sudakov and Verstraëte [12], Gao, Huo, Liu, and Ma [7] proved that every graph with no proper kk-coloring has k−1k-1 cycles of consecutive lengths. See also [8].

A graph with no proper kk-coloring has a subgraph with minimum degree at least kk, otherwise, the graph is (k−1)(k-1)-degenerate and thus has a proper kk-coloring. Dean [4] conjectured that for k≥3k \ge3, every graph with minimum degree at least kk has a cycle of length 0 modulo kk. This conjecture was proved for k=3k=3 by Chen and Saito [2] and for k=4k=4 by Dean, Lesniak, and Saito [5]. Recently, Luo, Ma, and Zhao [10] proved Dean’s conjecture for every k≥6k \ge6, leaving only the case k=5k=5 open.

Once existence is guaranteed, a natural followup question is a quantitative question: given a graph with no proper kk-coloring, what is the guaranteed number of cycles of length 0 modulo kk? For k≥3k \ge3, the complete graph Kk+1K_{k+1} has no proper kk-coloring and has (k+1)(k−1)!2=(k+1)!2k(k+1)\frac{(k-1)!}{2}=\frac{(k+1)!}{2k} cycles of length 0 modulo kk. Note that the only possible cycles of length 0 modulo kk in Kk+1K_{k+1} are kk-cycles. Brewster, McGuinness, Moore, and Noel [1] conjectured that among all graphs with no proper kk-coloring, Kk+1K_{k+1} minimizes the number of cycles of length 0 modulo kk.

Conjecture 1 (Brewster, McGuinness, Moore, and Noel [1]). For every k≥3k \ge3, every graph with no proper kk-coloring has at least (k+1)!2k\frac{(k+1)!}{2k} cycles of length 0 modulo kk.

Brewster, McGuinness, Moore, and Noel [1] proved the following factorial lower bound, which is smaller than the conjectured bound by a factor of k+1k+1.

Theorem 2 (Brewster, McGuinness, Moore, and Noel [1]). For every k≥3k \ge3, every graph with no proper kk-coloring has at least (k−1)!2\frac{(k-1)!}{2} cycles of length 0 modulo kk.

Strengthening results in [13], Moore and West [11] proved further counting results regarding the number of cycles of certain lengths modulo kk through a given edge. They also proved that for k≥3k \ge3, every graph with no proper kk-coloring has k!2\frac{k!}{2} cycles of length 1 modulo kk. Note that this bound is sharp as again demonstrated by Kk+1K_{k+1}. For the number of cycles of length 0 modulo kk in a graph with no proper kk-coloring, their results guarantee (k−1)!2\frac{(k-1)!}{2} cycles, recovering the result in Theorem 2.

Kim and Picollelli [9] confirmed Conjecture 1 for k=3k=3. We establish Conjecture 1 for every k≥3k \ge3.

Theorem 3. For every k≥3k \ge3, every graph with no proper kk-coloring has at least (k+1)!2k\frac{(k+1)!}{2k} cycles of length 0 modulo kk.

Recall that the bound of (k+1)!2k\frac{(k+1)!}{2k} is tight by Kk+1K_{k+1}.

Our proof uses the approach of Brewster, McGuinness, Moore, and Noel [1]. Relative to a vertex ordering, an akak-cycle is good if it can be traversed with at most aa 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 HH has no proper kk-coloring but H−vH-v has a proper kk-coloring, then every ordering induced by a proper kk-coloring of H−vH-v, with vv placed last, has at least k+1k+1 good cycles. In § 3, we show that a fixed cycle is good for at most 2k2k permutations of the colors of a fixed proper kk-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 k+1k+1 yield at least k+1k+1 good cycles. We begin with a recoloring lemma.

Fix k≥3k \ge3. Let HH be a graph. Given a labeling φ:V(H)→Z\varphi: V(H) \to\mathbb{Z}, an edge xyxy is φ\varphi-monochromatic if φ(x)≡φ(y)(modk)\varphi(x) \equiv\varphi(y) \pmod{k}. Let D(H,φ)D(H,\varphi) be the digraph on V(H)V(H) where xy→\overrightarrow{xy} is an arc if and only if xy∈E(H)xy \in E(H) and φ(y)−φ(x)≡1(modk)\varphi(y)-\varphi(x) \equiv1 \pmod{k}. Thus a directed path of length rr increases the label by rr, modulo kk. Clearly, D(H,φ)D(H,\varphi) 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 k≥3k \ge3, let HH be a graph with χ(H)>k\chi(H)>k, and let φ:V(H)→Z\varphi: V(H) \to\mathbb{Z} be a labeling of HH. For each φ\varphi-monochromatic edge ee, let the two endpoints be t(e)t(e) and h(e)h(e). Then there exist φ\varphi-monochromatic edges e1,e2e_1,e_2 such that t(e1)t(e_1) can reach h(e2)h(e_2) in D(H,φ)D(H,\varphi).

Proof. Let MM be the set of φ\varphi-monochromatic edges of HH. Since HH has no proper kk-coloring, MM is nonempty; otherwise, replacing each label φ(v)\varphi(v) with φ(v)\varphi(v) modulo kk is a proper kk-coloring of HH, a contradiction. Let RR be the set of vertices reachable in D(H,φ)D(H,\varphi) from t(e)t(e) for some e∈Me \in M. Note that t(e)∈Rt(e) \in R for every e∈Me \in M.

Suppose to the contrary that h(e)∉Rh(e) \notin R for every e∈Me \in M. Define a labeling ψ:V(H)→{0,…,k−1}\psi: V(H) \to\{0,\ldots,k-1\} where ψ(u)≡\psi(u) \equiv

{φ(u)+1(modk),u∈R,φ(u)(modk),u∉R.\begin{cases} \varphi(u)+1 \pmod{k}, & u \in R,\\ \varphi(u) \pmod{k}, & u \notin R. \end{cases}

Every edge e∈Me \in M is properly colored by ψ\psi, since t(e)∈Rt(e) \in R and h(e)∉Rh(e) \notin R. Assume xyxy is monochromatic by ψ\psi. Thus xy∉Mxy \notin M and without loss of generality let x∈Rx \in R and y∉Ry \notin R. Since ψ(x)=ψ(y)\psi(x)=\psi(y), we know φ(y)−φ(x)≡1(modk)\varphi(y)-\varphi(x) \equiv1 \pmod{k}. Thus, xy→\overrightarrow{xy} is an arc of D(H,φ)D(H,\varphi). Since x∈Rx \in R, this implies y∈Ry \in R, a contradiction. Thus ψ\psi is a proper kk-coloring of HH, a contradiction.

Let H≺H_{\prec} denote the graph HH with an ordering ≺\prec on its vertices. A traversal of an edge xy∈E(H≺)xy \in E(H_{\prec}) from xx to yy is forward if x≺yx \prec y and backward otherwise. For a cycle CC in H≺H_{\prec}, let C⃗\vec{C} denote CC with one of the two cyclic traversals fixed. We call C⃗\vec{C} good if CC has length akak and C⃗\vec{C} has at most aa backward edges. We also call CC good if one of its two cyclic traversals is good. Note that the two cyclic traversals cannot be both good. One has bb backward edges and the other has ak−bak-b backward edges. If both were good, then ak≤a+b≤2aak \le a+b \le2a, which contradicts k≥3k \ge3.

Lemma 5. For k≥3k \ge3, let HH be a graph with χ(H)>k\chi(H)>k. Suppose HH has a vertex vv such that H−vH-v has a proper kk-coloring φ:V(H−v)→{0,…,k−1}\varphi: V(H-v) \to\{0,\ldots,k-1\}. Let ≺\prec be a vertex ordering of HH obtained by ordering the vertices of H−vH-v in nondecreasing order of their colors under φ\varphi, and placing vv last. Then H≺H_{\prec} has at least k+1k+1 distinct good cycles.

Proof. Extend φ\varphi to V(H)V(H) by setting φ(v)=k−1\varphi(v)=k-1. Let Z={z∈NH(v):φ(z)=k−1}Z=\{z \in N_H(v): \varphi(z)=k-1\}. Since HH has no proper kk-coloring, ZZ is nonempty. The only φ\varphi-monochromatic edges of HH are zvzv for z∈Zz \in Z. Let D=D(H,φ)D=D(H,\varphi).

We prove the lemma in four steps. First, we define k+1k+1 new labelings φi\varphi_i obtained by modifying φ\varphi. Second, to the endpoints of each φi\varphi_i-monochromatic edge, we assign t(e)t(e) and h(e)h(e). Third, using Lemma 4, we find a good cycle CiC_i for each i∈{1,…,k+1}i \in\{1,\ldots,k+1\} containing a specific vertex tit_i. Finally, we show that these k+1k+1 good cycles are pairwise distinct by these tit_i's.

Step 1. New labelings φi\varphi_i.

For a vertex uu, let dist⁡(u)\operatorname{dist}(u) denote the length of a shortest directed path from vv to uu in DD, and let dist⁡(u)=∞\operatorname{dist}(u)=\infty if uu is not reachable from vv. Note that each arc increases the label by 11, modulo kk. For z∈Zz \in Z, every finite dist⁡(z)\operatorname{dist}(z) is a positive multiple of kk since φ(z)=φ(v)\varphi(z)=\varphi(v). In particular, dist⁡(z)≥k\operatorname{dist}(z) \ge k.

For i∈{0,…,k+1}i \in\{0,\ldots,k+1\}, let Si={u∈V(H):dist⁡(u)≤i−1}S_i=\{u \in V(H):\operatorname{dist}(u) \le i-1\}. Note that S0=∅S_0=\varnothing and S1={v}S_1=\{v\}. Let TiT_i be the set of vertices that can reach some vertex of ZZ in D−SiD-S_i. We remark that paths of length 00 are allowed. Since S0⊆S1⊆⋯⊆Sk+1S_0 \subseteq S_1 \subseteq\cdots\subseteq S_{k+1}, we know T0⊇T1⊇⋯⊇Tk+1T_0 \supseteq T_1 \supseteq\cdots\supseteq T_{k+1}. Each vertex u∈Tiu \in T_i satisfies dist⁡(u)≥i\operatorname{dist}(u) \ge i and has a directed path to ZZ entirely inside TiT_i. For z∈Zz \in Z, we have z∈Tiz \in T_i if and only if dist⁡(z)≥i\operatorname{dist}(z) \ge i. Since dist⁡(v)=0\operatorname{dist}(v)=0, we have v∉T1v \notin T_1, in particular, v∉Tiv \notin T_i for i≥1i \ge1.

For i∈{1,…,k+1}i \in\{1,\ldots,k+1\}, define a new labeling φi:V(H)→Z\varphi_i:V(H)\to\mathbb{Z} by decreasing the label of each vertex in TiT_i by exactly 11. Note that vertices in T0T_0 receive a label of −1-1 under φi\varphi_i. Let Di=D(H,φi)D_i=D(H,\varphi_i).

Step 2. Assigning h(e)h(e) and t(e)t(e) to endpoints of φi\varphi_i-monochromatic edges.

For each φi\varphi_i-monochromatic edge ee of HH, we assign h(e)h(e) and t(e)t(e) to its endpoints as follows.

First, let e=xye=xy be a newly φi\varphi_i-monochromatic edge. Up to renaming xx and yy if necessary, xy→\overrightarrow{xy} is an arc of DD where x∉Tix \notin T_i, y∈Tiy \in T_i, and φ(y)−φ(x)≡1(modk)\varphi(y)-\varphi(x)\equiv1 \pmod{k}. Let (t(e),h(e))=(x,y)(t(e),h(e))=(x,y).

We claim dist⁡(x)+1=i=dist⁡(y)\operatorname{dist}(x)+1=i=\operatorname{dist}(y) and x∈Ti−1∖Tix \in T_{i-1}\setminus T_i. Indeed, let PP be a directed path from yy to ZZ entirely in TiT_i, which exists since y∈Tiy \in T_i. If dist⁡(x)≥i\operatorname{dist}(x)\ge i, then xy→\overrightarrow{xy} followed by PP shows that x∈Tix \in T_i, a contradiction, so dist⁡(x)≤i−1\operatorname{dist}(x)\le i-1. Since y∈Tiy \in T_i, we know i≤dist⁡(y)≤dist⁡(x)+1≤ii\le\operatorname{dist}(y)\le\operatorname{dist}(x)+1\le i, so dist⁡(x)=i−1\operatorname{dist}(x)=i-1 and dist⁡(y)=i\operatorname{dist}(y)=i. Moreover, xy→\overrightarrow{xy} followed by PP is a directed path from xx to ZZ in D−Si−1D-S_{i-1}, so x∈Ti−1x \in T_{i-1}.

Now, consider an originally φ\varphi-monochromatic edge zvzv of HH, so z∈Zz \in Z. If z∈Tiz \in T_i, then φi(v)−φi(z)=1\varphi_i(v)-\varphi_i(z)=1, so zv→\overrightarrow{zv} is an arc of DiD_i. Otherwise, z∉Tiz \notin T_i, so zv→\overrightarrow{zv} remains φi\varphi_i-monochromatic and dist⁡(z)<i≤k+1\operatorname{dist}(z)<i\le k+1. Let t(zv)=zt(zv)=z and h(zv)=vh(zv)=v. Since dist⁡(z)\operatorname{dist}(z) is a positive multiple of kk, we know dist⁡(z)=k\operatorname{dist}(z)=k and i=k+1i=k+1, so z∈Tk∖Tk+1z \in T_k\setminus T_{k+1}.

Consequently, every φi\varphi_i-monochromatic edge ee has

dist⁡(t(e))=i−1,t(e)∈Ti−1∖Ti,(1)\operatorname{dist}(t(e))=i-1,\qquad t(e)\in T_{i-1}\setminus T_i, \tag*{(1)}

and either h(e)∈Tih(e)\in T_i or i=k+1i=k+1 and h(e)=vh(e)=v.

Step 3. Good cycles for φi\varphi_i.

We first show that every directed cycle in DiD_i is good for ≺\prec. Note that i≥1i\ge1.

Let xyxy be an edge of H≺H_{\prec} with x≺yx\prec y. If xyxy is not φ\varphi-monochromatic, then 1≤φ(y)−φ(x)≤k−11\le\varphi(y)-\varphi(x)\le k-1. Since the label of an endpoint may change by exactly 11 under φi\varphi_i, we know 0≤φi(y)−φi(x)≤k0\le\varphi_i(y)-\varphi_i(x)\le k. Otherwise, xyxy is φ\varphi-monochromatic, so y=vy=v, φ(x)=k−1\varphi(x)=k-1, and x≺yx\prec y. Since v∉Tiv\notin T_i, we know φi(y)−φi(x)∈{0,1}\varphi_i(y)-\varphi_i(x)\in\{0,1\}. Hence, 0≤φi(y)−φi(x)≤k0\le\varphi_i(y)-\varphi_i(x)\le k for every edge xyxy with x≺yx\prec y. Since every arc xy→\overrightarrow{xy} of DiD_i satisfies φi(y)−φi(x)≡1(modk)\varphi_i(y)-\varphi_i(x)\equiv1\pmod{k}, we know φi(y)−φi(x)=1\varphi_i(y)-\varphi_i(x)=1 if x≺yx\prec y and φi(y)−φi(x)=1−k\varphi_i(y)-\varphi_i(x)=1-k if y≺xy\prec x.

Now let C⃗\vec{C} be a directed ℓ\ell-cycle in DiD_i with bb backward edges. Since 0=∑xy→∈A(C⃗)(φi(y)−φi(x))=(ℓ−b)+b(1−k)=ℓ−kb0=\sum_{\overrightarrow{xy}\in A(\vec{C})}(\varphi_i(y)-\varphi_i(x))=(\ell-b)+b(1-k)=\ell-kb, we know ℓ=kb\ell=kb, so C⃗\vec{C} is good.

We next show that DiD_i contains a directed cycle through some vertex of Ti−1∖TiT_{i-1}\setminus T_i. Recall the assignment of h(e)h(e) and t(e)t(e) for each φi\varphi_i-monochromatic edges from Step 2. By Lemma 4, there are φi\varphi_i-monochromatic edges e1,e2e_1,e_2 such that t(e1)t(e_1) can reach h(e2)h(e_2) in DiD_i. Let (ti,hi)=(t(e1),h(e2))(t_i,h_i)=(t(e_1),h(e_2)). We claim that hih_i can reach tit_i in DiD_i through vv. We first show hih_i can reach vv. By (1), either hi=vh_i=v and i=k+1i=k+1 or hi∈Tih_i\in T_i. If hi=vh_i=v, then there is nothing to show. Otherwise, hi∈Tih_i\in T_i, so there is a directed path in DD from hih_i to some z∈Zz\in Z entirely inside TiT_i. Since the labels of vertices on this path decrease by exactly 1 under φi\varphi_i, the path remains directed in DiD_i. Moreover, z∈Tiz\in T_i and v∉Tiv\notin T_i, so φi(v)−φi(z)=1\varphi_i(v)-\varphi_i(z)=1. Thus zv→\overrightarrow{zv} is an arc of DiD_i, so hih_i can reach vv.

By (1), dist⁡(ti)=i−1\operatorname{dist}(t_i)=i-1, there is a shortest directed path PP from vv to tit_i in DD. Every vertex uu on PP satisfies dist⁡(u)<i\operatorname{dist}(u)<i, so no vertex on PP is in TiT_i. Therefore, the labels of vertices on PP are unchanged under φi\varphi_i, so PP remains a directed path in DiD_i.

Combining these paths gives a closed directed walk from tit_i to hih_i to vv back to tit_i in DiD_i. This walk is nonempty since ti≠hit_i\ne h_i. Indeed, hi∈Tih_i\in T_i implies ti∉Tit_i\notin T_i and if hi=vh_i=v, then i=k+1i=k+1 so dist⁡(ti)=k>0=dist⁡(v)\operatorname{dist}(t_i)=k>0=\operatorname{dist}(v).

A shortest nonempty closed directed walk in DiD_i starting and ending at tit_i is a directed cycle through tit_i. Let CiC_i be its underlying cycle. As shown above, CiC_i is good, and ti∈V(Ci)∩(Ti−1∖Ti)t_i\in V(C_i)\cap(T_{i-1}\setminus T_i).

Step 4. Counting distinct good cycles.

Suppose Ci=C=CjC_i=C=C_j for some i<ji<j. Since a good cycle has only one good cyclic traversal, CiC_i and CjC_j are traversed in the same direction in DiD_i and DjD_j. Thus, for z∈{i,j}z\in\{i,j\} and for each edge xyxy on CzC_z traversed from xx to yy, φz(y)−φz(x)=1\varphi_z(y)-\varphi_z(x)=1 if x≺yx\prec y and φz(y)−φz(x)=1−k\varphi_z(y)-\varphi_z(x)=1-k if y≺xy\prec x. Thus φi(y)−φi(x)=φj(y)−φj(x)\varphi_i(y)-\varphi_i(x)=\varphi_j(y)-\varphi_j(x), which implies that φj−φi\varphi_j-\varphi_i is constant on the vertices of CC.

On the other hand, since i<ji<j, we have Tj⊆TiT_j\subseteq T_i. For each vertex u∈Ti∖Tju\in T_i\setminus T_j on CC, we have φi(u)=φ(u)−1\varphi_i(u)=\varphi(u)-1 and φj(u)=φ(u)\varphi_j(u)=\varphi(u). Also, φi(u)=φj(u)\varphi_i(u)=\varphi_j(u) when u∈Tju\in T_j or u∉Tiu\notin T_i.

Therefore, φj(u)−φi(u)={1,u∈Ti∖Tj,0,otherwise.\varphi_j(u)-\varphi_i(u)=\begin{cases} 1, & u\in T_i\setminus T_j, \\ 0, & \text{otherwise}. \end{cases} Since ti∉Tit_i\notin T_i, φj(ti)−φi(ti)=0\varphi_j(t_i)-\varphi_i(t_i)=0. However, by (1), tj∈Tj−1∖Tj⊆Ti∖Tjt_j\in T_{j-1}\setminus T_j\subseteq T_i\setminus T_j, so φj(tj)−φi(tj)=1\varphi_j(t_j)-\varphi_i(t_j)=1. Since ti,tjt_i,t_j are on CC, this contradicts that φj−φi\varphi_j-\varphi_i is constant on vertices of CjC_j.

Therefore C1,…,Ck+1C_1,\ldots,C_{k+1} 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 k≥3k\ge3, let HH be a graph with a vertex vv where φ:V(H−v)→{0,…,k−1}\varphi:V(H-v)\to\{0,\ldots,k-1\} is a proper kk-coloring. For each permutation π\pi of the kk colors, let ≺π\prec_\pi be the vertex ordering of HH obtained by ordering the vertices of H−vH-v in nondecreasing order of their colors under φ\varphi according to π\pi, and placing vv last. Then, each kk-cycle in HH is good in H≺πH_{\prec_\pi} for at most 2k2k permutations π\pi.

Proof. Fix a kk-cycle CC, and fix a cyclic traversal C⃗\vec C. We show that at most kk permutations π\pi make C⃗\vec C good.

(∗)(*) We first observe that any kk consecutive edges of C⃗\vec C not involving vv must contain a backward edge. Otherwise, the colors of the k+1k+1 vertices on the kk edges would be strictly increasing in the order specified by π\pi, which contradicts that there are kk colors. Case 1. CC avoids vv.

Partition the akak edges of CC into aa parts, where each part has kk consecutive edges on CC. By (∗)(*), each part contains a backward edge, so there are at least aa backward edges. If C⃗\vec{C} is good, then there must be exactly aa backward edges. This further implies that there are exactly k−1k-1 forward edges between two closest backward edges.

Consequently, the kk vertices following each backward edge have all kk colors, appearing in the order specified by π\pi. In particular, the same ordering of all kk colors appears aa times around C⃗\vec{C}.

To determine a permutation π\pi for which C⃗\vec{C} is good, we only need to choose which of the kk colors comes first. The order of the remaining k−1k-1 colors is then uniquely determined by their circular order along C⃗\vec{C}. Thus there are at most kk permutations π\pi for which C⃗\vec{C} is good.

Case 2. CC contains vv.

Let C⃗=u1u2…uak−1v\vec{C}=u_1u_2\ldots u_{ak-1}v. Since vv is last in ≺π\prec_\pi, the edge vu1vu_1 is backward, while the edge uak−1vu_{ak-1}v is forward. If C⃗\vec{C} is good, then at most a−1a-1 edges in E(C)∖{vu1,uak−1v}E(C)\setminus\{vu_1,u_{ak-1}v\} are backward.

Consider the last (a−1)k(a-1)k edges of the path u1u2…uak−1u_1u_2\ldots u_{ak-1}. Partition these edges into a−1a-1 parts where each part has kk consecutive edges. By (∗)(*), each of the a−1a-1 parts contains at least one backward edge. It follows that u1u2,u2u3,…,uk−2uk−1u_1u_2,u_2u_3,\ldots,u_{k-2}u_{k-1} are forward edges, so φ(u1),φ(u2),…,φ(uk−1)\varphi(u_1),\varphi(u_2),\ldots,\varphi(u_{k-1}) are distinct and appear in increasing order according to π\pi.

These k−1k-1 colors determine their relative order in π\pi. There are exactly kk possible positions to insert the unique missing color in {0,1,…,k−1}∖{φ(u1),…,φ(uk−1)}\{0,1,\ldots,k-1\}\setminus\{\varphi(u_1),\ldots,\varphi(u_{k-1})\}. Thus at most kk permutations π\pi make C⃗\vec{C} good.

Since CC has two possible cyclic traversals, and C⃗\vec{C} is good for at most kk permutations, we conclude CC is good for at most 2k2k permutations.

The conclusion

We now prove Theorem 3. Given an integer k≥3k\geq3, let GG be a graph with χ(G)>k\chi(G)>k. Since χ(G)>k\chi(G)>k, let HH be an induced subgraph of GG with the minimum number of vertices where χ(H)>k\chi(H)>k and every vertex-minimal subgraph H′H' of HH satisfies χ(H′)≤k\chi(H')\leq k. Fix v∈V(H)v\in V(H). By minimality, H−vH-v has a proper kk-coloring φ\varphi. Consider all k!k! permutations π\pi of the kk colors and their induced vertex orderings ≺π\prec_\pi. For each π\pi, relabel the colors so that their increasing order agrees with π\pi.

By Lemma 5, each H≺πH_{\prec_\pi} has at least k+1k+1 good cycles. Since each cycle is good for at most 2k2k permutations by Lemma 6, HH contains at least k!(k+1)2k=(k+1)!2k\frac{k!(k+1)}{2k}=\frac{(k+1)!}{2k} cycles whose lengths are divisible by kk. Since every cycle of HH is also a cycle of GG, the desired lower bound follows.

To see that the bound is sharp, consider Kk+1K_{k+1}. Note that χ(Kk+1)=k+1\chi(K_{k+1})=k+1. There are k+1k+1 ways to choose the kk vertices of a kk-cycle. For every choice of kk vertices, there are (k−1)!2\frac{(k-1)!}{2} distinct kk-cycles. Thus Kk+1K_{k+1} has exactly (k+1)(k−1)!2=(k+1)!2k(k+1)\frac{(k-1)!}{2}=\frac{(k+1)!}{2k} cycles of length divisible by kk.

Further questions

Our result determines the minimum number of cycles of length 00 modulo kk among graphs with no proper kk-coloring. More generally, Brewster, McGuinness, Moore, and Noel [1] explicitly suggested studying the same question for cycles of length rr modulo kk. (See also the discussion in the last section of [13]. Let Nk,r(G)N_{k,r}(G) denote the number of cycles of GG with length rr modulo kk. We have shown that every graph GG with no proper kk-coloring satisfies Nk,0(G)≥Nk,0(Kk+1)N_{k,0}(G) \ge N_{k,0}(K_{k+1}). As mentioned in the introduction, Moore and West [11] proved the analogous inequality for r=1r=1. For r=2r=2, the inequality holds since Nk,2(Kk+1)=0N_{k,2}(K_{k+1})=0. Thus, it is natural to ask if this phenomenon continues:

Question 7. Let k≥4k \ge4 and r∈{3,…,k−1}r \in\{3,\ldots,k-1\}. Does every graph GG with no proper kk-coloring satisfy Nk,r(G)≥Nk,r(Kk+1)N_{k,r}(G) \ge N_{k,r}(K_{k+1})?

Another question is to characterize equality in Theorem 3. It is natural to restrict attention to critical graphs. Recall that a graph GG is kk-critical if χ(G)=k\chi(G)=k and every proper subgraph of GG has a proper (k−1)(k-1)-coloring. Kim and Picollelli [9] showed that K4K_4 is the only 4-critical graph with exactly four cycles of length 0 modulo 3. We ask whether this extends to larger values of kk.

Question 8. Let k≥4k \ge4. Is Kk+1K_{k+1} the unique (k+1)(k+1)-critical graph with exactly (k+1)!2k\frac{(k+1)!}{2k} cycles of length 0 modulo kk?

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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [13]Zsolt Tuza. Graph coloring in linear time. J. Combin. Theory Ser. B, 55(2):236–243, 1992.DOI

Paper details

vlnc:W_j5wbqezn
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 11

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

GPT (multiple versions)

View statement
Looking for related papers…
Contents