Given an integer c, an edge colored graph G is said to be rainbow c-splittable if it can be decomposed into at most c vertex-disjoint monochromatic induced subgraphs of distinct colors. We provide a polynomial-time algorithm for deciding whether an edge-colored complete graph is rainbow c-splittable. For not necessarily complete graphs, we show that the problem is polynomial if c = 2, whereas for c >= 3 it is NP-complete even if the graph has maximum degree 2c - 1. Finally, it remains NP-complete even for 2-edge colored graphs of maximum degree 7c - 14. (C) 2011 Elsevier B.V. All rights reserved.
Monti, Angelo; Sinaimeri, Blerina. (2011). Rainbow graph splitting. THEORETICAL COMPUTER SCIENCE, (ISSN: 0304-3975), 412:39, 5315-5324. Doi: 10.1016/j.tcs.2011.06.004.
Rainbow graph splitting
Blerina Sinaimeri
2011
Abstract
Given an integer c, an edge colored graph G is said to be rainbow c-splittable if it can be decomposed into at most c vertex-disjoint monochromatic induced subgraphs of distinct colors. We provide a polynomial-time algorithm for deciding whether an edge-colored complete graph is rainbow c-splittable. For not necessarily complete graphs, we show that the problem is polynomial if c = 2, whereas for c >= 3 it is NP-complete even if the graph has maximum degree 2c - 1. Finally, it remains NP-complete even for 2-edge colored graphs of maximum degree 7c - 14. (C) 2011 Elsevier B.V. All rights reserved.
Pubblicazioni consigliate
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
