On a certain complexity estimate in graph theory (Q1358054)

From MaRDI portal
scientific article
Language Label Description Also known as
English
On a certain complexity estimate in graph theory
scientific article

    Statements

    On a certain complexity estimate in graph theory (English)
    0 references
    14 August 1997
    0 references
    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''.
    0 references
    first-order theory
    0 references
    \(n\)-theory
    0 references
    weakly saturated graph
    0 references
    connected component
    0 references
    block
    0 references
    cycle
    0 references
    weakly saturated model
    0 references
    cutpoint
    0 references

    Identifiers

    0 references
    0 references
    0 references
    0 references
    0 references