Department of
Mathematical Sciences
Colloquium Series
Math Logo
"A short construction of highly chromatic digraphs without short cycles"
Mike Severino
PhD Candidate, University of Montana
A natural digraph analogue of the graph-theoretic 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:34-38, (1959)], it was shown probabilistically in [D. Bokal et al., The circular chromatic number of a digraph, J. Graph Theory, 46(3): 227-240, 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