$K_r$-packing of $P_4$-tidy graphs

The $K_r$-packing problem asks for the maximum number of pairwise vertex-disjoint cliques of size $r$ in a graph, for a fixed integer $r \geq 2$. This problem is NP-hard for general graphs when $r \geq 3$, and even when restricted to chordal graphs. However, Guruswami et al. proposed a polynomial-time algorithm for cographs (when $r$ is fixed). In this work we extended this algorithm to $P_4$-tidy graphs, keeping the same time complexity.

2009