Boundary properties of graphs

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, Bollobás 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.