Partitioning a split graph into induced subgraphs isomorphic to the path of order 3.
О. И. Дугинов · Proceedings of the National Academy of Sciences of Belarus Physics and Mathematics Series · 2019
The study of the computational complexity of problems on graphs is an urgent problem. We show that the problem of deciding whether the vertex set of a given split graph of order 3n can be partitioned into induced subgraphs isomorphic to P3 is a polynomially solvable problem. We develop a polynomial-time algorithm based on the method of augmenting graphs. The developed efficient algorithm can be used for solving team formation problems.