The Proper Interval Colored Graph problem for caterpillar trees: (Extended Abstract)

This paper studies the computational complexity of the Proper interval colored graph problem (picg), when the input graph is a colored caterpillar, parameterized by hair length. To prove our result we also study a graph layout problem the Proper colored layout problem (pclp). We show a dichotomy result: the picg and the pclp are NP-complete for colored caterpillars of hair length ≥ 2, while both problems are in P, for colored caterpillars of hair length < 2.