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\mod r\) in \(G\).  Also, \(G-e\) contains at least half that many cycles of length \(0\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}\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\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)