Department of

July 2021 August 2021 September 2021 Su Mo Tu We Th Fr Sa Su Mo Tu We Th Fr Sa Su Mo Tu We Th Fr Sa 1 2 3 1 2 3 4 5 6 7 1 2 3 4 4 5 6 7 8 9 10 8 9 10 11 12 13 14 5 6 7 8 9 10 11 11 12 13 14 15 16 17 15 16 17 18 19 20 21 12 13 14 15 16 17 18 18 19 20 21 22 23 24 22 23 24 25 26 27 28 19 20 21 22 23 24 25 25 26 27 28 29 30 31 29 30 31 26 27 28 29 30

Tuesday, August 24, 2021

**Abstract:** Tuza [1992] proved that a graph $G$ with no cycles of length congruent to $1$ modulo $k$ is $k$-colorable. For $2\le r\le k$, we prove that if $G$ has an edge $e$ such that $G-e$ is $k$-colorable and $G$ is not, then $e$ lies in at least $(k-1)!/(k-r)!$ cycles of length $1{\,\mathrm{mod}\,} r$ in $G$, and $G-e$ contains at least $(1/2)(k-1)!/(k-r)!$ cycles of length $0 {\,\mathrm{mod}\,} r$.

A $(k,d)$-coloring of $G$ is a homomorphism from $G$ to the graph with vertex set $Z_k$ defined by making $i$ and $j$ adjacent if $d\le j-i \le k-d$. Assume $\gcd(k,d)=1$, and let $s=d^{-1}{\,\mathrm{mod}\,} k$. Zhu [2002] proved that $G$ is $(k,d)$-colorable when $G$ has no cycle $C$ with length congruent to $is$ modulo $k$ for any $i\in \{1,...,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 $is {\,\mathrm{mod}\,} k$ for some $i$ in $\{1,...,d\}$.

These results are joint work with Benjamin R. Moore.