Universal graphs with forbidden subgraphs and algebraic closure. (English) Zbl 0928.03049
The authors investigate the problem of existence of countable universal graphs with finitely many forbidden subgraphs. They use model-theoretic notions to obtain their results. So they work with existentially closed models and investigate the growth rate of the algebraic closure of finite sets.
In the first half of the paper they provide the model-theoretic notions and methods which they need for their investigations. In the second half these methods are applied. Many proofs for known examples are simplified. Further on they give many new examples of universal graphs omitting a finite set of connected finite graphs.
In the first half of the paper they provide the model-theoretic notions and methods which they need for their investigations. In the second half these methods are applied. Many proofs for known examples are simplified. Further on they give many new examples of universal graphs omitting a finite set of connected finite graphs.
Reviewer: M.Weese (Potsdam)
MSC:
| 03C98 | Applications of model theory |
| 05C75 | Structural characterization of families of graphs |
| 03C15 | Model theory of denumerable and separable structures |
Keywords:
model completeness; existential completeness; existence of countable universal graphs; finitely many forbidden subgraphs; existentially closed models; growth rate of the algebraic closure of finite setsReferences:
| [1] | Bacsich, P., The strong amalgamation property, Colloq. Math., 33, 13-23 (1975) · Zbl 0331.02033 |
| [2] | Bondy, J. A.; Murty, U. S.R., Graph Theory with Applications (1979), North-Holland: North-Holland Amsterdam · Zbl 0453.00012 |
| [3] | Chang, C. C.; Keisler, H. J., Model Theory (1990), North-Holland: North-Holland Amsterdam · Zbl 0697.03022 |
| [4] | Cherlin, G.; Komjáth, P., There is no universal countable pentagon-free graph, J. Graph Theory, 18, 337-341 (1994) · Zbl 0805.05044 |
| [5] | Cherlin, G.; Shi, N., Graphs omitting sums of complete graphs, J. Graph Theory, 24, 237-247 (1997) · Zbl 0868.05023 |
| [6] | Cherlin, G.; Shi, N., Graphs omitting a finite set of cycles, J. Graph Theory, 21, 351-355 (1996) · Zbl 0845.05060 |
| [7] | Cherlin, G.; Shi, N.; Tallgren, L., Graphs omitting a bushy tree, J. Graph Theory, 26, 203-210 (1997) · Zbl 0918.05041 |
| [8] | Erdös, P.; Gallai, T., On maximal paths and circuits of graphs, Acta Math., Acad. Sci. Hung., 10, 337-356 (1959) · Zbl 0090.39401 |
| [9] | Füredi, Z.; Komjáth, P., On the existence of countable universal graphs, J. Graph Theory, 25, 53-58 (1997) · Zbl 0878.05064 |
| [10] | Füredi, Z.; Komjáth, P., Nonexistence of universal graphs without some trees, Combinatorica, 17, 163-171 (1997) · Zbl 0889.05038 |
| [11] | Goldstern, M.; Kojman, M., Universal arrow free graphs, Acta. Math. Hungar., 73, 319-326 (1996) · Zbl 0921.05052 |
| [12] | Hirschfeld, J.; Wheeler, W. H., Forcing, Arithmetic, Division Rings (1975), Springer-Verlag: Springer-Verlag Berlin · Zbl 0304.02024 |
| [14] | Komjáth, P.; Mekler, A.; Pach, J., Some universal graphs, Israel J. Math., 64, 158-168 (1988) · Zbl 0672.05074 |
| [15] | Komjáth, P.; Pach, J., Universal graphs without large bipartite subgraphs, Mathematika, 31, 282-290 (1984) · Zbl 0551.05057 |
| [16] | Komjáth, P.; Pach, J., Universal elements and the complexity of certain classes of infinite graphs, Discrete Math., 95, 255-270 (1991) · Zbl 0756.05097 |
| [17] | Pach, J., A problem of Ulam on planar graphs, European J. Combin., 2, 357-361 (1981) · Zbl 0469.05027 |
| [18] | Rado, R., Universal graphs and universal functions, Acta Arith., 9, 331-340 (1964) · Zbl 0139.17303 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
