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 neighbour of a different colour from its own). We say that P is acyclic if for any parts P, P0 of P, the bipartite subgraph G[P, P0] consisting of the edges between P and P0 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; an d we shall denote by ad(d) the maximum over all graphs G of maximum degree at most d of ad(G ). In this paper, we prove that ad(3) = 2, which establishes a conjecture of Boiron, Sopena and Vignal. For general d, we prove the upper bound ad(d) = O(d ln d) and a lower bound of a d(d) = Omega(d).
Joint work with Louigi Addario-Berry and Ross J. Kang.