Fragmented coloring of proper interval and split graphs

We study the fragmented coloring problem which is a generalization of the vertex coloring problem. A (λ,C)(λ,C)-fragmented coloring of a graph GG is an assignment of a color from {0,…,λ−1}{0,…,λ−1} to each vertex of GG such that every connected component in the graph induced by vertices of a single color has at most CC vertices. For proper interval graphs, we give linear time and nearly linear time algorithms for the problems of minimizing λλ given CC, and minimizing CC given λλ. We also consider versions in which each vertex has a weight, and the sum of the weights in each induced connected component must be at most CC. We give nearly linear time algorithms for the splittable weighted version and a 2-approximation for the non-splittable weighted version, all on proper interval graphs. We also prove that even the unweighted version is NP-hard for split graphs.