Vertex coloring acyclic digraphs and their corresponding hypergraphs

Geir Agnarsson, Agust Egilsson, Magnus Mar Halldorsson

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…