Problem in graph theory (Q1239167): Difference between revisions
From MaRDI portal
Added link to MaRDI item. |
Removed claims |
||
Property / author | |||
Property / author: Sergey V. Petrov / rank | |||
Property / reviewed by | |||
Property / reviewed by: Dragos Cvetković / rank | |||
Revision as of 16:49, 22 February 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Problem in graph theory |
scientific article |
Statements
Problem in graph theory (English)
0 references
1976
0 references
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\)).
0 references