Skip to main content

Brooks-type results for coloring of digraphs

Resource type
Thesis type
(Thesis) Ph.D.
Date created
2011-06-06
Authors/Contributors
Abstract
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.
Document
Identifier
etd6768
Copyright statement
Copyright is held by the author.
Permissions
The author granted permission for the file to be printed and for the text to be copied and pasted.
Scholarly level
Supervisor or Senior Supervisor
Thesis advisor: Mohar, Bojan
Member of collection
Download file Size
etd6768_AHarutyunyan.pdf 1.06 MB

Views & downloads - as of June 2023

Views: 26
Downloads: 1