Partitioning permutations into increasing and decreasing subsequences

A permutation is an (r, s)-permutation if it can be partitioned into r increasing and s decreasing, possibly empty subsequences. For any fixed non-negative integers r and s, the family of (r, s)-permutations is characterized by a finite list of forbidden subsequences. This is derived from a more general graph-theoretic proof showing that, for any fixed non-negative integers r and s, the family of perfect graphs whose vertex set admits a partition into r cliques and s independent sets if characterized by a finite list of forbidden induced subgraphs.