Date
Tue, 16 Feb 2010
Time
14:30 - 15:30
Location
L3
Speaker
Vadim Lozin
Organisation
Warwick

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 of labeled graphs 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-width and their speed of growth is

superfactorial, while the limit property of this sequence (i.e., the acyclic graphs) has bounded

tree-width and its speed of growth is factorial. To overcome this difficulty, the notion of

boundary properties of graphs has been recently introduced. In the present talk, we use this

notion in order to identify some classes of graphs which are well-quasi-ordered with

respect to the induced subgraph relation.

Please contact us with feedback and comments about this page. Last updated on 03 Apr 2022 01:32.