Vertex coloring acyclic digraphs and their corresponding hypergraphs

Details Vertex coloring acyclic digraphs and their corresponding hypergraphs Vertex coloring acyclic digraphs and their corresponding hypergraphs

2007-06-11

arxiv.org/abs/0706.1539v1

Mathematics

Combinatorics

15 pages

Scientific paper

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)$.

Affiliated with

Also associated with

No associations

Rating

Vertex coloring acyclic digraphs and their corresponding hypergraphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Vertex coloring acyclic digraphs and their corresponding hypergraphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Vertex coloring acyclic digraphs and their corresponding hypergraphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-179896