Discrete Applied Math Seminar by Doug West: Cycles in Color-Critical Graphs.

Speaker: Douglas B. West, Zhejiang Normal University and University of Illinois Urbana-Champaign

Title: Cycles in Color-Critical Graphs

Abstract:
Tuza [1992] proved that a graph $G$ having no cycles of length congruent to $1$ modulo $k$ is $k$-colorable. We strengthen this by proving for $2\le r\le k$ that any edge $e$ such that $G-e$ is $k$-colorable and $G$ is not lies in at least $\prod _{i=1}^{r-1}(k-i)$ cycles of length $1\mathrm{mod}r$ in $G$.  Also, $G-e$ contains at least half that many cycles of length $0\mathrm{mod}r$.

We also consider an analogue of Tuza's result for circular coloring.
A it $(k,d)$-coloring of a graph $G$ is a homomorphism from $G$ to the graph with vertex set $Z_k$ and edge set $\{ij:d\le j-i\le k-d\}$. With $k$ and $d$ relatively prime, let $s=d^{-1}\mathrm{mod}k$. Zhu [2002] proved
that $G$ has a $(k,d)$-coloring 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.

Seminar Contacts: Hemanshu Kaul (kaul@iit.edu) and Samantha Dahlberg (sdahlberg@iit.edu)