Vertex coloring acyclic digraphs and their corresponding hypergraphsReport as inadecuate



 Vertex coloring acyclic digraphs and their corresponding hypergraphs


Vertex coloring acyclic digraphs and their corresponding hypergraphs - Download this document for free, or read online. Document in PDF available to download.

Download or read this book online for free in PDF: Vertex coloring acyclic digraphs and their corresponding hypergraphs
We consider vertex coloring of an acyclic digraph $\Gdag$ in such a way that two vertices which have a common ancestor in $\Gdag$ receive distinct colors. Such colorings arise in a natural way when bounding space for various genetic data for efficient analysis. We discuss the corresponding {\em down-chromatic number} and derive an upper bound as a function of $D\Gdag$, 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 $\Gdag$ and $D\Gdag$.



Author: Geir Agnarsson; Agust Egilsson; Magnus Mar Halldorsson

Source: https://archive.org/







Related documents