Acyclic Dominating Partitions

Given a graph G = (V, E), let P be a partition of V. We say that P is dominating if, for each part P of P, the set V\P is a dominating set in G (equivalently, if every vertex has a neighbor of a different part from its own). We say that P is acyclic if for any parts P, P'of P, the bipartite subgraph G[P, P'] consisting of the edges between P and P' in P contains no cycles. The acyclic dominating number ad(G) of G is the least number of parts in any partition of V that is both acyclic and dominating; and we shall denote by ad(d) the maximum over all graphs G of maximum degree at most d of ad(G). In this article, we prove that ad(3) = 2, which establishes a conjecture of P. Boiron, E. Sopena, and L. Vignal, DIMACS/DIMATIA Conference "Contemporary Trends in Discrete Mathematics", 1997, pp. 1-10. For general d, we prove the upper bound ad(d), = O(dIn d) and a lower bound of ad(d) = Omega(d). (C) 2009 Wiley Periodicals, Inc. J Graph Theory 64: 292-311, 2010