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 ⌈log3 n ⌉ (resp. ⌈log3 n⌉+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 asymp-totically sharp for an infinite family of interval graphs. In addition, some results are derived for related problems