Article ID Journal Published Year Pages File Type
418851 Discrete Applied Mathematics 2015 9 Pages PDF
Abstract

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.

Related Topics
Physical Sciences and Engineering Computer Science Computational Theory and Mathematics
Authors
, , ,