On partitioning interval graphs into proper interval subgraphs and related problems
In this paper, we establish that any interval graph (resp. circular-arc graph) with n vertices admits a partition into at most ?log3n? (resp. ?log3n? + 1) proper interval subgraphs, for n>1. The proof is constructive and provides an efficient algorithm to compute such a partition. On the other hand, this bound is shown to be asymptotically sharp for an infinite family of interval graphs. In addition, some results are derived for related problems.  2010 Wiley Periodicals, Inc. J Graph Theory 68:38-54, 2011
interval graphs circular-arc graphs proper interval graphs graph partitioning problems efficient graph algorithms