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. - 412:39(2011), pp. 5315-5324. [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.
2011
algorithms; complexity; edge-coloring; vertex partition
Rainbow graph splitting / Monti, Angelo; Sinaimeri, Blerina. - In: THEORETICAL COMPUTER SCIENCE. - ISSN 0304-3975. - 412:39(2011), pp. 5315-5324. [10.1016/j.tcs.2011.06.004]
File in questo prodotto:
Non ci sono file associati a questo prodotto.
Pubblicazioni consigliate

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11385/202503
Citazioni
  • Scopus 2
  • ???jsp.display-item.citation.isi??? 1
social impact