Colored-independence on Paths

Abstract

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=\mathrm{\varnothing }$. In particular, ${\beta }_{\mathrm{P}\mathrm{R}\mathrm{T}}(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.