Component Coloring of Proper Interval Graphs and Split Graphs

Details Component Coloring of Proper Interval Graphs and Split Graphs Component Coloring of Proper Interval Graphs and Split Graphs

2012-01-16

arxiv.org/abs/1201.3273v1

Computer Science

Discrete Mathematics

15 pages, 5 figures

Scientific paper

We introduce a generalization of the well known graph (vertex) coloring problem, which we call the problem of \emph{component coloring of graphs}. Given a graph, the problem is to color the vertices using minimum number of colors so that the size of each connected component of the subgraph induced by the vertices of the same color does not exceed $C$. We give a linear time algorithm for the problem on proper interval graphs. We extend this algorithm to solve a weighted version of the problem in which vertices have integer weights and can be split into differently colored parts, so that the total weight of a monochromatic component does not exceed $C$. We also prove that the problem is NP-hard for split graphs.

Affiliated with

Also associated with

No associations

Rating

Component Coloring of Proper Interval Graphs and Split Graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Component Coloring of Proper Interval Graphs and Split Graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Component Coloring of Proper Interval Graphs and Split Graphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-410293