MSO2_2-orderability conjecture for VR-equational classes with property SEP

Let C\mathcal{C} be a VR-equational class of graphs. Say that C\mathcal{C} has property SEP\mathsf{SEP} when it satisfies the separation property defined in the surrounding theory. The VR-equational MSO2_2-orderability conjecture. Every VR-equational class that has property SEP\mathsf{SEP} is MSO2\mathrm{MSO}_2-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

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.