



Mike Severino PhD Candidate, University of Montana 

A natural digraph analogue of the graphtheoretic concept of an 'independent set' is that of an 'acyclic set', namely a set of vertices not spanning a directed cycle. Hence a digraph analogue of a graph coloring is a decomposition of the vertex set into acyclic sets. In the spirit of a famous theorem of P. Erdős [Graph theory and probability, Canad. J. Math., 11:3438, (1959)], it was shown probabilistically in [D. Bokal et al., The circular chromatic number of a digraph, J. Graph Theory, 46(3): 227240, 2004] that there exist digraphs with arbitrarily large girth and chromatic number. Here I give a construction of such digraphs.  
Monday, 5 May 2014 3:10 p.m. in Math 103 4:00 p.m. Refreshments in Math Lounge 109 

Spring 2014 Colloquia & Events Mathematical Sciences  University of Montana 
