On a certain complexity estimate in graph theory
type: Item
instance of: scholarly article
title: On a certain complexity estimate in graph theory
zbMATH Open document ID: 0874.03044
DOI: 10.1007/BF02104862
published in: Siberian Mathematical Journal
publication date: 1997-08-14T00:00:00Z
review text: A first-order theory \(T\) is said to be an \(n\)-theory if each formula is equivalent in \(T\) to a Boolean combination of formulas with at most \(n\) free variables. For a weakly saturated graph \(\Gamma\), the author gives a sufficient condition for its theory to be an \(n\)-theory. Unfortunately, there are some mistakes in the translation, for example, a correcter translation of the title is ``On a certain complexity estimate of theories of graphs'' and the term ``cutpoint'' should be used instead of the term ``junction point''.
Mathematics Subject Classification ID: 03C50
Mathematics Subject Classification ID: 05C75
Mathematics Subject Classification ID: 03C65
zbMATH DE Number: 1023956
zbMATH Keywords: first-order theory
zbMATH Keywords: \(n\)-theory
zbMATH Keywords: weakly saturated graph
zbMATH Keywords: connected component
zbMATH Keywords: block
zbMATH Keywords: cycle
zbMATH Keywords: weakly saturated model
zbMATH Keywords: cutpoint
author: S. V. Sudoplatov
MaRDI profile type: Publication
cites work: Superstable graphs
description: scientific article; zbMATH DE number 1023956