Partitioning permutations into increasing and decreasing subsequences (Q1906146)

A permutation is called an \((r, s)\)-permutation if it can be partitioned into \(r\) increasing and \(s\) decresing, possible empty subsequences. In this paper the authors give a forbidden subsequence characterization of the family of \((r, s)\)-permutations for any fixed \(r\) and \(s\). This result follows from a more general graph theoretic result showing that for any fixed nonnegative integers \(r\) and \(s\), the family of perfect graphs whose vertex set admits a partition into \(r\) cliques and \(s\) independent sets (that is, has a particular type of cocoloring) is characterized by a finite list of forbidden induced subgraphs.