Cycles in color-critical graphs (Q2121717)

Summary: \textit{Z. Tuza} [J. Comb. Theory, Ser. B 55, No. 2, 236--243 (1992; Zbl 0709.05019)] proved that a graph with no cycles of length congruent to \(1\) modulo \(k\) is \(k\)-colorable. We prove that if a graph \(G\) has an edge \(e\) such that \(G-e\) is \(k\)-colorable and \(G\) is not, then for \(2\leqslant r\leqslant k\), the edge \(e\) lies in at least \(\prod_{i=1}^{r-1} (k-i)\) cycles of length \(1\mod r\) in \(G\), and \(G-e\) contains at least \(\frac12{\prod_{i=1}^{r-1} (k-i)}\) cycles of length \(0 \pmod r\). A \((k, d)\)-coloring of \(G\) is a homomorphism from \(G\) to the graph \(K_{k:d}\) with vertex set \(\mathbb{Z}_k\) defined by making \(i\) and \(j\) adjacent if \(d\leqslant j-i \leqslant k-d\). When \(k\) and \(d\) are relatively prime, define \(s\) by \(sd\equiv 1\pmod k\). A result of \textit{X. Zhu} [J. Comb. Theory, Ser. B 86, No. 1, 109--113 (2002; Zbl 1025.05028)] implies that \(G\) is \((k, d)\)-colorable when \(G\) has no cycle \(C\) with length congruent to \(\mathfrak{is} \pmod k\) for any \(i\in \{1, \ldots, 2d-1\}\). In fact, only \(d\) classes need be excluded: we prove that if \(G-e\) is \((k, d)\)-colorable and \(G\) is not, then \(e\) lies in at least one cycle with length congruent to \(\mathfrak{is} \pmod k\) for some \(i\) in \(\{1, \ldots, d\}\). Furthermore, if this does not occur with \(i\in\{1,\ldots,d-1\}\), then \(e\) lies in at least two cycles with length \(1 \pmod k\) and \(G-e\) contains a cycle of length \(0 \pmod k\).