Acyclic Systems of Representatives and Acyclic Colorings of Digraphs

摘要

A natural digraph analog of the graph theoretic concept of "an independent set" is that of "an acyclic set of vertices," namely a set not spanning a directed cycle. By this token, an analog of the notion of coloring of a graph is that of decomposition of a digraph into acyclic sets. We extend some known results on independent sets and colorings in graphs to acyclic sets and acyclic colorings of digraphs. In particular, we prove bounds on the topological connectivity of the complex of acyclic sets, and using them we prove sufficient conditions for the existence of acyclic systems of representatives of a system of sets of vertices. These bounds generalize a result of Tardos and Szabo. We prove a fractional version of a strong-acyclic-coloring conjecture for digraphs. (c) 2008 Wiley Periodicals, Inc. J Graph Theory 59: 177-189, 2008