Universal graphs with a forbidden subtree (Q875935): Difference between revisions

Let \(C\) be a finite connected graph. A graph \(G\) is \(C\)-free if it contains no subgraph which is isomorphic to \(C\). A countable graph \(G\) is weakly universal (strongly universal) if every countable \(C\)-free graph is isomorphic to an (induced) subgraph of \(G\). The authors deal with the problem of determining the finite connected constraint graphs \(C\) for which there is a countable universal \(C\)-free graph. They confirm a long-standing Tree Conjecture of Tallgren: For a finite tree \(T\) the following are equivalent: (i) There is a weakly universal \(T\)-free graph. (ii) There is a strongly universal \(T\)-free graph. (iii) \(T\) is a path or a near path (that is a tree which is not a path but is obtained from a path by attaching one edge with one additional vertex). The paper is organized as follows: In Section 1 the authors give an overview about the problem of determining universal graphs. They describe the results obtained so far and the main techniques used to deal with the problem. They discuss the main open problems in this field. In Section 2 they describe the ``tree of blocks'', which is assigned to a graph. They introduce a new idea which allows an inductive analysis of universality problems according to the complexity of the underlying tree. With this method, universality problems can be reduced to canonical ``minimal'' cases, called ``critical''. In Section 3 the authors show that the Tree Conjecture holds for trees with a unique vertex of maximal degree. This is done by using the methods of Section 2. In the following five chapters the authors prove the full Tree Conjecture. This is done by making a very coarse division of the critical cases into subclasses according to the maximal vertex degree and the structure of the external vertices of maximal degree.