Vertex coloring acyclic digraphs and their corresponding hypergraphs ?
We consider vertex coloring of an acyclic digraph G ? in such a way that two vertices which have a common ancestor in G ? receive distinct colors. Such colorings arise in a natural way when bounding space for various genetic data for efficient analysis. We discuss the corresponding down-chromatic number  and derive an upper bound as a function of D ( G ? ) , the maximum number of descendants of a given vertex, and the degeneracy of the corresponding hypergraph. Finally, we determine an asymptotically tight upper bound of the down-chromatic number in terms of the number of vertices of G ? and D ( G ? ) .
05c15 05c20 05c65 05c85 05d90 06a06