Problem in graph theory
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\)).
This page was built for publication: Problem in graph theory
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1239167)
