Universal graphs for the topological minor relation. (English) Zbl 1526.05106
Summary: A subgraph-universal graph/a topological minor-universal graph in a class of graphs \(\mathcal{G}\) is a graph in \(\mathcal{G}\) which contains every graph in \(\mathcal{G}\) as a subgraph/topological minor. We prove that the class \(\mathcal{P}\) of all countable planar graphs does not contain a topological minor-universal graph. This answers a question of R. Diestel and D. Kühn [ibid. 32, No. 2, 191–206 (1999; Zbl 0932.05025)] and strengthens a result of J. Pach [Eur. J. Comb. 2, 357–361 (1981; Zbl 0469.05027)] stating that there is no subgraph-universal graph in \(\mathcal{P}\). Furthermore, we characterise for which subdivided stars \(T\) there is a topological minor-universal graph in the class of all countable \(T\)-free graphs.
© 2023 The Authors. Journal of Graph Theory published by Wiley Periodicals LLC.
© 2023 The Authors. Journal of Graph Theory published by Wiley Periodicals LLC.
MSC:
| 05C63 | Infinite graphs |
| 05C10 | Planar graphs; geometric and topological aspects of graph theory |
| 05C83 | Graph minors |
| 05C75 | Structural characterization of families of graphs |
| 05C60 | Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) |
References:
| [1] | G.Cherlin and S.Shelah, Universal graphs with a forbidden subtree, J. Combin. Theory Ser. B. 97 (2007), no. 3, 293-333. · Zbl 1116.03026 |
| [2] | G.Cherlinand S.Shelah, Universal graphs with a forbidden subgraph: Block path solidity, Combinatorica. 36 (2016), no. 3, 249-264. · Zbl 1389.05112 |
| [3] | G.Cherlinand L.Tallgren, Universal graphs with a forbidden near‐path or 2‐bouquet, J. Graph Theory. 56 (2007), no. 1, 41-63. · Zbl 1131.03013 |
| [4] | R.Diestel, On universal graphs with forbidden topological subgraphs, European J. Combin. 6 (1985), no. 2, 175-182. · Zbl 0581.05020 |
| [5] | R.Diestel, R.Halin, and W.Vogler, Some remarks on universal graphs, Combinatorica. 5 (1985), no. 4, 283-293. · Zbl 0619.05039 |
| [6] | R.Diesteland D.Kühn, A universal planar graph under the minor relation, J. Graph Theory. 32 (1999), no. 2, 191-206. · Zbl 0932.05025 |
| [7] | Z.Füredi and P.Komjáth, On the existence of countable universal graphs, J. Graph Theory. 25 (1997), no. 1, 53-58. · Zbl 0878.05064 |
| [8] | T.Huynh, B.Mohar, R.Šámal, C.Thomassen, and D. R.Wood, Universality in minor‐closed graph classes, Preprint, arXiv:2109.00327. (2021). |
| [9] | P.Komjáth, A.Mekler, and J.Pach, Some universal graphs, Israel J. Math. 64 (1988), no. 2, 158-168. · Zbl 0672.05074 |
| [10] | F.Lehner, Universal planar graphs for the topological minor relation, Preprint, arXiv:2203.03477. (2022). |
| [11] | J.Pach, A problem of Ulam on planar graphs, European J. Combin. 2 (1981), no. 4, 357-361. · Zbl 0469.05027 |
| [12] | R.Rado, Universal graphs and universal functions, Acta Arith. 9 (1964), no. 4, 331-340. · 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.
