Matched-factor d-domatic Colouring of Graphs
K.S. Sudeep
Chennai Mathematical Institute.
14-07-06

---

Abstract

We discuss the so-called d-domatic colourings of graphs. Consider a graph G and a collection of connected spanning subgraphs G_1, G_2, ..., G_k, not necessarily edge-disjoint. A subset U_i of the vertex set is said to be d-dominating 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 d-dominates G_i. They prove that k <= mu(k) and give an algorithmic proof that mu(k) <= ceil(3/2 (k-1)). 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 NP-complete. 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.