A Counterexample Regarding Labelled Well-Quasi-Ordering

Brignall, Robert; Engen, Michael and Vatter, Vincent (2018). A Counterexample Regarding Labelled Well-Quasi-Ordering. Graphs and Combinatorics, 34(6) pp. 1395–1409.

DOI: https://doi.org/10.1007/s00373-018-1962-0

Abstract

Korpelainen, Lozin, and Razgon conjectured that a hereditary property of graphs which is well-quasi-ordered by the induced subgraph order and defined by only finitely many minimal forbidden induced subgraphs is labelled well-quasi-ordered, a notion stronger than that of n-well-quasi-order introduced by Pouzet in the 1970s. We present a counterexample to this conjecture. In fact, we exhibit a hereditary property of graphs which is well-quasi-ordered by the induced subgraph order and defined by finitely many minimal forbidden induced subgraphs yet is not 2-well-quasi-ordered. This counterexample is based on the widdershins spiral, which has received some study in the area of permutation patterns.

Viewing alternatives

Metrics

Item Actions

Export

You can export this page using these formats Digital Object Identifier - DOI

About

• Item ORO ID
• 56865
• Item Type
• Journal Item
• ISSN
• 1435-5914
• Keywords
• labelled well-quasi-order; permutation graph; well-quasi-order; Widdershins spiral
• Academic Unit or School
• Faculty of Science, Technology, Engineering and Mathematics (STEM) > Mathematics and Statistics
  Faculty of Science, Technology, Engineering and Mathematics (STEM)
• Copyright Holders
• © 2018 Springer Japan KK, part of Springer Nature
• Depositing User
• Robert Brignall