Given an undirected graph G = (V, E) and a set P of paths of G, we investigate the path k-forest coloring problem, k being a fixed positive integer, aimed at deciding whether there exists a coloring of the paths in P with at most k colors so that paths with the same color form a forest of G. If paths with the same color share an edge we intend that no monochromatic cycle is formed. We show that this problem is NP-complete for each k ≥ 2, even in the restricted case where the length of any path in P is at most 2. For k = 1 it is known that the problem is polynomially solvable. We show other hardness results for the problem formulated on planar graphs, with k = 2 or k = 3.
Coloring of paths into forests
GALBIATI, GIULIA;GUALANDI, STEFANO
2013-01-01
Abstract
Given an undirected graph G = (V, E) and a set P of paths of G, we investigate the path k-forest coloring problem, k being a fixed positive integer, aimed at deciding whether there exists a coloring of the paths in P with at most k colors so that paths with the same color form a forest of G. If paths with the same color share an edge we intend that no monochromatic cycle is formed. We show that this problem is NP-complete for each k ≥ 2, even in the restricted case where the length of any path in P is at most 2. For k = 1 it is known that the problem is polynomially solvable. We show other hardness results for the problem formulated on planar graphs, with k = 2 or k = 3.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
