Metatheorems for decision problems on hyperedge replacement graph languages (Q1121675)

If a graph-theoretical property is compatible with the derivation process of hyperedge replacement graph grammars in a certain way, the property turns out to be decidable for the corresponding graph languages. More exactly speaking, we consider two questions: (1) Is there a graph in the generated language having the property? (2) Do all graphs in the generated language have the property? In both cases, we get decidability for all hyperedge replacement graph grammars as inputs. Colorability, Hamiltonicity, and planarity are shown to be compatible so that our decidability results apply to them.