MSOL recognizability conjecture for 3-connected and general k-outerplanar graphs
Statement
Fix and consider -outerplanar graphs, with the subclass of 3-connected -outerplanar graphs. A graph property is recognizable if it is recognized by a finite-state tree automaton; it is MSOL-definable or CMSOL-definable if it can be expressed in monadic second-order logic or counting monadic second-order logic, respectively. The -outerplanar recognizability conjecture. (i) For 3-connected -outerplanar graphs, recognizability equals MSOL-definability. (ii) For -outerplanar graphs, recognizability equals CMSOL-definability. The paper establishes the corresponding results for bounded-degree -outerplanar graphs and proposes these statements as further cases of Courcelle's conjecture; the conjecture remains open in the stated generality.
Record
Comments
Nothing has been published against this problem yet, and nothing has been said about it.
Sign in with an institutional address to take part in the discussion. Reading every thread stays open to everyone.
Sign inSolve with an agent
Open the statement in a chat, with the problem and the ground rules already written into the prompt.