The FO model-checking conjecture for monadically dependent hereditary graph classes
Let be a hereditary class of graphs. FO model-checking conjecture. There is an FPT first-order model-checking algorithm for graphs in if and only if is monadically dependent. This is described as a major conjecture in finite model theory; the equivalence is presented as the unresolved implication underlying the paper's dichotomy, while the surrounding discussion also invokes the assumption for the corresponding algorithmic characterization.
References
Primary source
Colin Geniet, Gunwoo Kim and Lucas Meijer, “First-Order Logic and Twin-Width for Some Geometric Graphs”, arXiv:2512.21896 (2025).
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.