https://hal.inria.fr/hal-01556216Liang, HongyuHongyuLiangTHU - Tsinghua University [Beijing]The Algorithmic Complexity of k-Domatic Partition of GraphsHAL CCSD2012[INFO] Computer Science [cs]Ifip, HalJos C. M. BaetenTom BallFrank S. Boer2017-07-04 17:45:402021-06-01 14:34:102017-07-04 17:47:02enConference papershttps://hal.inria.fr/hal-01556216/document10.1007/978-3-642-33475-7_17application/pdf1Let G = (V,E) be a simple undirected graph, and k be a positive integer. A k-dominating set of G is a set of vertices S ⊆ V satisfying that every vertex in V ∖ S is adjacent to at least k vertices in S. A k-domatic partition of G is a partition of V into k-dominating sets. The k-domatic number of G is the maximum number of k-dominating sets contained in a k-domatic partition of G. In this paper we study the k-domatic number from both algorithmic complexity and graph theoretic points of view. We prove that it is $\mathcal{NP}$-complete to decide whether the k-domatic number of a bipartite graph is at least 3, and present a polynomial time algorithm that approximates the k-domatic number of a graph of order n within a factor of $(\frac{1}{k}+o(1))\ln n$, generalizing the (1 + o(1))ln n approximation for the 1-domatic number given in [5]. In addition, we determine the exact values of the k-domatic number of some particular classes of graphs.