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.
Rainbow graph splitting / Monti, Angelo; Sinaimeri, Blerina. - In: THEORETICAL COMPUTER SCIENCE. - ISSN 0304-3975. - STAMPA. - 412:39(2011), pp. 5315-5324. [10.1016/j.tcs.2011.06.004]
Rainbow graph splitting
MONTI, Angelo;SINAIMERI, BLERINA
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.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
