CMU Campus
Department of         Mathematical Sciences
Events People Colloquia and Seminars Conferences Centers Positions Areas of Research About the Department Alumni
Algorithms, Combinatorics and Optimization Seminar
Jie Ma
Carnegie Mellon University
Title: 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

1) if a strongly connected digraph D contains no directed cycle of length 1 modulo k, then D is k-colorable;

2) 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.

In addition to strengthening several classical graph coloring results (by Bondy, Erdős and Hajnal, Gyárfás, etc), our results give an affirmative answer to a question of Tuza in 1992 and imply a strong form of a conjecture of Diwan, Kenkre and Vishwanathan: If graph 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.

Date: Thursday, October 2, 2014
Time: 3:30 pm
Location: Wean Hall 8220
Submitted by:  Bukh