Well-quasi-order for permutation graphs omitting a path and a clique

MaRDI QIDQ2344822zbMATH OpenFDO

Authors Aistis Atminas, Robert Brignall, Nicholas Korpelainen, Vadim Lozin, Vincent Vatter

Publication date 18 May 2015

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1312.5907, http://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i2p20

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

graphspermutation graphspermutationswell-quasi-order

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Exact enumeration problems, generating functions (05A15) Paths and cycles (05C38) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Structural characterization of families of graphs (05C75)

Abstract: We consider well-quasi-order for classes of permutation graphs which omit both a path and a clique. Our principle result is that the class of permutation graphs omitting $P_5$ and a clique of any size is well-quasi-ordered. This is proved by giving a structural decomposition of the corresponding permutations. We also exhibit three infinite antichains to show that the classes of permutation graphs omitting $P_6,K_6$, $P_7,K_5$, and $P_8,K_4$ are not well-quasi-ordered.

Review text

Summary: We consider well-quasi-order for classes of permutation graphs which omit both a path and a clique. Our principle result is that the class of permutation graphs omitting \(P_5\) and a clique of any size is well-quasi-ordered. This is proved by giving a structural decomposition of the corresponding permutations. We also exhibit three infinite antichains to show that the classes of permutation graphs omitting \(\{P_6,K_6\}\), \(\{P_7,K_5\}\), and \(\{P_8,K_4\}\) are not well-quasi-ordered.

Recommendations

• Two forbidden induced subgraphs and well-quasi-ordering
• Well-quasi-ordering versus clique-width
• Labelled well-quasi-order for permutation classes
• Well-quasi-ordering does not imply bounded clique-width
• Induced subgraphs and well‐quasi‐ordering

Cites work

• Bipartite induced subgraphs and well-quasi-ordering
• Generating and enumerating 321-avoiding and skew-merged simple permutations
• Geometric grid classes of permutations
• Graph minors. I. Excluding a forest
• Grid classes and partial well order
• Grid classes and the Fibonacci dichotomy for restricted permutations
• scientific article; zbMATH DE number 3332242 (Why is no real title available?)
• Inflations of geometric grid classes of permutations
• Labelled induced subgraphs and well-quasi-ordering
• On partial well-order for monotone grid classes of permutations
• Ordering by Divisibility in Abstract Algebras
• Profile classes and partial well-order for permutations
• Simple permutations and pattern restricted permutations
• Small permutation classes
• Subclasses of the separable permutations
• Subgraphs and well‐quasi‐ordering
• Transitiv orientierbare Graphen
• Two forbidden induced subgraphs and well-quasi-ordering

Cited in

(6)

• Profile classes and partial well-order for permutations
• Well-quasi-ordering versus clique-width
• On well quasi-order of graph classes under homomorphic image orderings
• Recent progress on well-quasi-ordering graphs
• Labelled well-quasi-order for permutation classes
• An antichain of monomial ideals in a twisted commutative algebra

This page was built for publication: Well-quasi-order for permutation graphs omitting a path and a clique

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