Document Type
Lecture
Publication Date
11-21-2014
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; and (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, Erdos and Hajnal, Gyarfas, etc), our results give an a rmative 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). Joint work with Zhibin Chen and Wenan Zang.
Relational Format
presentation
Recommended Citation
Ma, Jie, "Digraph Coloring and Forbidden Cycle" (2014). Combinatorics Seminar. 44.
https://egrove.olemiss.edu/math_combinatorics/44
