In this project we aim to study certain fundamental structures of directed graphs. A central notion appearing in the study of digraphs is that of a Directed Acyclic Graph (or DAG), a digraph without directed cycles. It is hard to overstate the role that DAGs play in computer science and discrete mathematics. Their applications in telecommunications, sorting, scheduling, data compression, and data processing are ubiquitous. Curiously enough, compared to their practical importance, fundamental knowledge and understanding of DAGs is not as broad or deep as one would like. The main goal of this project is to study how DAGs affect the structure and properties of digraphs which contain them, thus giving us insight into general understanding of arbitrary digraphs.
A related important problem is decomposing a general digraph into DAGs. In classical graph theory, such decompositions often lead to efficient algorithms. Here, given a general digraph D on n vertices, one would like to partition the vertices of D into, say, k parts such that the vertices of each part induce a DAG. The minimum integer k for which this can be done is defined to be the dichromatic number of D. Dichromatic theory is now a well-studied area and this project also aims to increase our understanding of this parameter.