Oct. 2, 3:30pm, Wean 8220

Jie Ma, Carnegie Mellon University

Relations between digraph colorings and cycle class

Jie Ma, Carnegie Mellon University

Relations between digraph colorings and cycle class

Abstract:

Let *k* and *r* be two integers with *k*≥ *2* and *k*≥ *r*≥ *1*. We show that *G* contains no cycle of length *r* modulo *k*, then
*G* is *k*-colorable if *r*≠ *2* and *(k+1)*-colorable otherwise. In this talk, we will also discuss other related results and mention sereval open problems (both graph theoretic and algorithmic). Most of the results presented are joint with Zhibin Chen and Wenan Zang.

- if a strongly
connected digraph
*D*contains no directed cycle of length*1*modulo*k*, then*D*is*k*-colorable; - if a digraph
*D*contains no directed cycle of length*r*modulo*k*, then*D*can be vertex-colored with*k*colors so that each color class induces an acyclic subdigraph.