Matched-Factor d -Domatic Coloring of Graphs
K. S. Sudeep, Sundar Vishwanathan · SIAM Journal on Discrete Mathematics · 2008
Consider a graph G and a collection of connected spanning subgraphs $G_1, G_2, \ldots, G_k$, not necessarily edge-disjoint. A subset $U_i$ of the vertex set is said to d-$dominate$ $G_i$ if in $G_i$, all the vertices are at distance at most d from some vertex in $U_i$. Alon et al. [Discrete Math., 262 (2003), pp. 17–25] introduced and studied a function $\mu(k)$, which is defined as the minimum radius of domination d such that the vertex set of every graph with a collection of k spanning subgraphs can be partitioned into $U_1, U_2, \ldots, U_k$ such that $U_i$ d-dominates $G_i$. They proved that $\mu(k) < \frac{3}{2}k$, and the proof yields a polynomial time algorithm for the same. We prove that the problem is $\cal NP$-complete, and we also answer a question from their paper by improving their bound to $(\frac{3}{2}-\epsilon)k$. We also present an algorithm which finds such a coloring in polynomial time.