Matchedfactor ddomatic Colouring of Graphs K.S. Sudeep Chennai Mathematical Institute. 140706 Abstract We discuss the socalled ddomatic colourings of graphs. Consider a graph G and a collection of connected spanning subgraphs G_1, G_2, ..., G_k, not necessarily edgedisjoint. A subset U_i of the vertex set is said to be ddominating G_i, if in G_i, all the vertices are at distance at most d from some vertex in U_i. Alon et.al. 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, ..., U_k such that U_i ddominates G_i. They prove that k <= mu(k) and give an algorithmic proof that mu(k) <= ceil(3/2 (k1)). We first prove that given two trees on the same vertex set, the problem of finding whether the vertex set can be partitioned into two parts such that vertices of one part is a dominating set in one of the trees and those of the other part is a dominating set in the other tree is NPcomplete. We then get an improved upper bound of (3/2  epsilon)k on mu(k) and present an algorithm that finds such a colouring in polynomial time. This is joint work with Sundar Vishwanathan.
