Vertex coloring acyclic digraphs and their corresponding hypergraphs

Simple item page
dc.creatorAgnarsson, Geir
dc.creatorEgilsson, Agust
dc.creatorHalldorsson, Magnus Mar
dc.date2007-06-11
dc.date.accessioned2026-07-07T08:04:58Z
dc.date.available2026-07-07T08:04:58Z
dc.descriptionWe 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)$.
dc.description15 pages
dc.identifierhttps://arxiv.org/abs/0706.1539
dc.identifierhttp://arxiv.org/abs/0706.1539
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/130154
dc.subjectCombinatorics
dc.subject05C15, 05C20
dc.titleVertex coloring acyclic digraphs and their corresponding hypergraphs
dc.typetext

Files

Collections

arXiv