Partitioning permutations into increasing and decreasing subsequences

DOI10.1016/S0097-3165(96)80012-4MaRDI QIDQ1906146zbMATH OpenOpenAlexFDO

Authors André E. Kézdy, Chi Wang, Hunter Snevily

Publication date 26 February 1996

Published in Journal of Combinatorial Theory. Series A (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/s0097-3165(96)80012-4

cocoloring forbidden induced subgraphs forbidden subsequence characterization partition perfect graphs permutation

Permutations, words, matrices (05A05) Coloring of graphs and hypergraphs (05C15) Generalized Ramsey theory (05C55) Graph theory (05C99)

Review text

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.

Cites work

Cited in

(20)

This page was built for publication: Partitioning permutations into increasing and decreasing subsequences

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1906146)