Record Details

Matched-factor d-domatic coloring of graphs

DSpace at IIT Bombay

View Archive Info
 
 
Field Value
 
Title Matched-factor d-domatic coloring of graphs
 
Creator SUDEEP, KS
VISHWANATHAN, S
 
Subject graph theory
algorithms
domination
matched-factor domatic number
 
Description 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 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,..., U-k such that Ui d-dominates Gi. They proved that mu(k) < 3/2 k, and the proof yields a polynomial time algorithm for the same. We prove that the problem is NP-complete, and we also answer a question from their paper by improving their bound to (3/2-epsilon)k. We also present an algorithm which finds such a coloring in polynomial time.
 
Publisher SIAM PUBLICATIONS
 
Date 2011-08-29T05:20:44Z
2011-12-26T12:58:25Z
2011-12-27T05:48:20Z
2011-08-29T05:20:44Z
2011-12-26T12:58:25Z
2011-12-27T05:48:20Z
2007
 
Type Article
 
Identifier SIAM JOURNAL ON DISCRETE MATHEMATICS, 21(4), 1071-1082
0895-4801
http://dx.doi.org/10.1137/060662307
http://dspace.library.iitb.ac.in/xmlui/handle/10054/11974
http://hdl.handle.net/10054/11974
 
Language en