We introduce the colored decompositions framework, in which vertices of the graph can be equipped with colors, and in which the goal is to find decompositions of this graph that do not separate the color classes. In this paper, we give two linear time algorithms for the colored modular and split decompositions of graphs, and we apply them to give linear time algorithms for the modular and split decompositions of trigraphs, which improves a result of Thomasse, Trotignon and Vuskovic (2013). As a byproduct, we introduce the non-separating families that allow us to prove that those two decompositions have the same properties on graphs and on trigraphs.
展开▼
