Korpelainen et al.'s conjecture on finite definition and labelled well-quasi-ordering

Let C\mathcal{C} be a hereditary graph class, meaning that it is closed under taking induced subgraphs, and suppose that C\mathcal{C} 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 C\mathcal{C} 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

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.