The Open UniversitySkip to content
 

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.

Full text available as:
Full text not publicly available (Accepted Manuscript)
Due to publisher licensing restrictions, this file is not available for public download until 10 October 2019
Click here to request a copy from the OU Author.
DOI (Digital Object Identifier) Link: https://doi.org/10.1007/s00373-018-1962-0
Google Scholar: Look up in Google Scholar

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.

Item Type: Journal Item
Copyright Holders: 2018 Springer Japan KK, part of Springer Nature
ISSN: 1435-5914
Keywords: labelled well-quasi-order; permutation graph; well-quasi-order; Widdershins spiral
Academic Unit/School: Faculty of Science, Technology, Engineering and Mathematics (STEM) > Mathematics and Statistics
Faculty of Science, Technology, Engineering and Mathematics (STEM)
Item ID: 56865
Depositing User: Robert Brignall
Date Deposited: 05 Nov 2018 11:25
Last Modified: 03 May 2019 23:15
URI: http://oro.open.ac.uk/id/eprint/56865
Share this page:

Metrics

Altmetrics from Altmetric

Citations from Dimensions

Actions (login may be required)

Policies | Disclaimer

© The Open University   contact the OU