Colored-independence on Paths

We consider a storage/scheduling problem which, in addition to the standard restriction involving pairs of elements that cannot be placed together, considers pairs of elements that must be placed together. A set \( S \) is a colored-independent set if, for each color class \( V_i \), \( S \cap V_i = V_i \) or \( S \cap V_i = \emptyset \). In particular, \( \beta_{\mathrm{PRT}}(G) \), the independence-partition number, is determined for all paths of order \( n \). Finally, we show that the resulting decision problem for graphs is NP-complete even when the input graph is a path.