The FO model-checking conjecture for monadically dependent hereditary graph classes
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.
Sources & referencesView supporting material
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
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.