Vadim Lozin
Mathematics Institute
Boundary properties of graphs
ABSTRACT:
The notion of a boundary graph
property is a relaxation of that of a
minimal property. Several fundamental
results in graph theory have
been obtained in terms of identifying
minimal properties. For
instance, Robertson and Seymour showed that
there is a unique minimal
minor-closed property with unbounded tree-width
(the planar graphs),
while Balogh, Bollobas and Weinreich identified
nine minimal
hereditary properties with the factorial speed
of growth.
However, there are situations where
the notion of minimal property is
not applicable. A typical example of
this type is given by graphs of
large girth. It is known that for each
particular value of k, the
graphs of girth at least k are of
unbounded tree-, clique- or rank-
width and their speed of growth is superfactorial, while the "limit"
property of this sequence (i.e., acyclic
graphs) has bounded tree-,
clique- and rank-width and its speed of
growth is factorial. To
overcome this difficulty, we introduce the
notion of boundary
properties of graphs and identify some of them
with respect to
various graph problems.