Problem in graph theory
type: Item
instance of: scholarly article
title: Problem in graph theory
zbMATH Open document ID: 0358.05030
published in: Automation and Remote Control
publication date: 1976-01-01T00:00:00Z
review text: 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\)).
Mathematics Subject Classification ID: 05C99
Mathematics Subject Classification ID: 94C10
Mathematics Subject Classification ID: 68W99
zbMATH DE Number: 3557822
author: S. V. Petrov
reviewed by: Dragoš Cvetković
MaRDI profile type: Publication
description: scientific article; zbMATH DE number 3557822