Factor \(d\)-domatic colorings of graphs (Q1868834)

Consider a graph and a collection of (not necessarily edge-disjoint) connected spanning subgraphs (factors) of the graph. In this paper the problem of coloring the vertices of the graph so that each color class of the vertices dominates each factor is considered. Let \(\alpha (t,k)\) be the minimum radius of domination \(d\) such that every graph with a collection of \(k\) factors can be vertex colored with \(t\) colors so that each color class \(d\)-dominates each factor. Similarly, given an integer \(k\), let \(\mu (k)\) denote the minimum \(d(k)\) such that every \(k\)-factorization of every graph on at least \(k\) vertices admits a matched-factor \(d(k)\)-domatic coloring. Upper and lower bounds on \(\alpha (t,k)\) are proposed (i.e., for every \(k\geq 2\) and \(t\geq k\), \(\alpha (t,k)\leq \lceil 3(kt-1)/2\rceil \)). It is surprising that the upper bound is finite and does not depend on the order of the graph. It is also shown that for every \(k\geq 2\), \(k\leq \mu (k)\leq \lceil 3(k-1)/2\rceil \).