Tuza [1992] 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 $2leq rleq k$, the edge $e$ lies in at least $prod_{i=1}^{r-1}(k-i)$ cycles of length $1mod r$ in $G$, and $G-e$ contains at least $frac{1}{2}prod_{i=1}^{r-1}(k-i)$ cycles of length $0 mod 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 $dleq j-i leq k-d$. When $k$ and $d$ are relatively prime, define $s$ by $sdequiv 1mod k$. A result of Zhu [2002] implies that $G$ is $(k,d)$-colorable when $G$ has no cycle $C$ with length congruent to $is$ modulo $k$ for any $iin {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 $ismod k$ for some $i$ in ${1,ldots,d}$. Furthermore, if this does not occur with $iin{1,ldots,d-1}$, then $e$ lies in at least two cycles with length $1mod k$ and $G-e$ contains a cycle of length $0 mod k$.
Download