MSO-orderability conjecture for VR-equational classes with property SEP
MSO-orderability conjecture for VR-equational classes with property SEP
Let be a VR-equational class of graphs. Say that has property when it satisfies the separation property defined in the surrounding theory. The VR-equational MSO-orderability conjecture. Every VR-equational class that has property is -orderable. The corresponding statement is established in the paper for HR-equational classes, but decidability is not obtained for VR-equational classes; the conjecture proposes that the same implication holds for all VR-equational classes.
Sources & referencesView supporting material
Primary source
Achim Blumensath and Bruno Courcelle, “Monadic second-order definable graph orderings”, arXiv:1310.8148 (2014).
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.