Problem in graph theory (Q1239167)

The letters of an alphabet are used to mark the vertices of graphs. The rules of the grammar act on marked graphs replacing in them certain subgraphs by others. The rules are first applied to graphs from a certain set of marked graphs and their successive action generates the language of the grammar. In the paper two such grammars are constructed: one generating all planar triangulations, another - all such triangulations having chromatic number 4 together with all their colourings by 4 colours. In the first case the alphabet contains 1 letter and in the second one 4 letters. In both cases the starting triangulations are triangles. The rules are of two types: \(1^0\) Rules introducing a new vertex and three edges subdividing a triangle into three new triangles. \(2^0\) Rules switching edges common to two triangles. (If \(v_1v_2\) is an edge common to triangles \(v_1v_2v_3\) and \(v_1v_2v_4\) then the rule replaces the edge \(v_1v_2\) with the edge \(v_3v_4\)).