The maximal-antichain conjecture for paths and tree classes
The maximal-antichain conjecture for paths and tree classes
Let denote the class of paths, let denote the class of rooted trees of height at most , and let denote the first-order transduction quasiorder. A collection of graph classes is a maximal antichain when its members are pairwise incomparable under this quasiorder and no further class can be added while preserving incomparability. The maximal-antichain conjecture for paths and tree classes. The pairs
are all the maximal antichains containing . This is presented as an equivalent formulation of the preceding shrubdepth characterization and concerns the structure of antichains in the first-order transduction quasiorder. The source does not specify whether it has been resolved.
Sources & referencesView supporting material
Primary source
Jaroslav Nesetril, Patrice Ossona de Mendez and Sebastian Siebertz, “Structural properties of the first-order transduction quasiorder”, arXiv:2010.02607 (2021).
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.