Boundary properties of graphs
|
Tue, 16/02/2010 14:30 |
Vadim Lozin (Warwick) |
Combinatorial Theory Seminar  |
L3 |
| 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. | |||