Korpelainen et al.'s conjecture on finite definition and labelled well-quasi-ordering
Korpelainen et al.'s conjecture on finite definition and labelled well-quasi-ordering
Let be a hereditary graph class, meaning that it is closed under taking induced subgraphs, and suppose that is well-quasi-ordered under the induced subgraph relation. The class is labelled well-quasi-ordered if, for every well-quasi-order of labels, its labelled graphs contain no infinite antichain under the labelled induced subgraph relation. Korpelainen et al.'s conjecture. The class is finitely defined if and only if it is labelled well-quasi-ordered. Every labelled well-quasi-ordered class is already known to be finitely defined, so the open part is the converse for well-quasi-ordered hereditary classes.
Sources & referencesView supporting material
Primary source
Aistis Atminas and Robert Brignall, “Well-quasi-ordering and finite distinguishing number”, arXiv:1512.05993 (2019).
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.