In the thesis, the coloring of digraphs is studied. The chromatic number of a digraph D is the smallest integer k so that the vertices of D can be partitioned into at most k sets each of which induces an acyclic subdigraph. A set of four topics on the chromatic number is presented. First, the dependence of the chromatic number of digraphs on the maximum degree is explored. An analog of Gallai's Theorem is proved and some algorithmic questions involving list colorings are studied. Secondly, an upper bound on the chromatic number of digraphs without directed cycles of length two is obtained, strengthening the upper bound of Brooks' Theorem by a multiplicative factor of α < 1. Thirdly, evidence is provided for the global nature of the digraph chromatic number by proving that sparse digraphs with maximum degree Δ can have chromatic number as large as Ω(Δ/ log Δ), as well as showing the existence of digraphs with arbitrarily large chromatic number where every constant fraction of the vertices is 2-colorable. Finally, a generalization of digraph coloring to acyclic homomorphisms is considered, and a result linking D-colorability and girth is presented.
Copyright is held by the author.
The author granted permission for the file to be printed and for the text to be copied and pasted.
Supervisor or Senior Supervisor
Thesis advisor: Mohar, Bojan
Member of collection