×

Every infinitely edge-connected graph contains the Farey graph or \({T_{\aleph_0}\ast t}\) as a minor. (English) Zbl 1486.05212

Summary: We show that every infinitely edge-connected graph contains the Farey graph or \(T_{\aleph_0}\ast t\) as a minor. These two graphs are unique with this property up to minor-equivalence.

MSC:

05C63 Infinite graphs
05C55 Generalized Ramsey theory
05C40 Connectivity
05C83 Graph minors
05C10 Planar graphs; geometric and topological aspects of graph theory
05D10 Ramsey theory
05C75 Structural characterization of families of graphs
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Bruhn, H.; Diestel, R., Duality in infinite graphs, Combin. Probab. Comput., 15, 75-90 (2006) · Zbl 1082.05028 · doi:10.1017/S0963548305007261
[2] Clay, M., Margalit, D.: Office Hours with a Geometric Group Theorist. Princeton University Press, Princeton (2017). doi:10.23943/princeton/9780691158662.001.0001
[3] Diestel, R.: Graph Theory, 5th edn. Springer, New York (2016). doi:10.1007/978-3-662-53622-3
[4] Diestel, R.: Abstract separation systems. Order 35(1), 157-170 (2018). doi:10.1007/s11083-017-9424-5. https://arxiv.org/abs/1406.3797v6 · Zbl 1469.06006
[5] Diestel, R.: Tree sets. Order 35(1), 171-192 (2018). doi:10.1007/s11083-017-9425-4. https://arxiv.org/abs/1512.03781v3 · Zbl 1412.06002
[6] Geelen, J., Joeris, B.: A Generalization of the Grid Theorem (2016). https://arxiv.org/abs/1609.09098
[7] Gollin, J.P., Heuer, K.: Characterising k-connected sets in infinite graphs (2018). https://arxiv.org/abs/1811.06411
[8] Halin, R.: Simplicial decompositions of infinite graphs, Advances in Graph Theory. Ann. Discrete Math. (1978). doi:10.1016/S0167-5060(08)70500-4
[9] Hatcher, A.: Topology of Numbers (book in preparation) (2017). https://pi.math.cornell.edu/ hatcher/TN/TNbook.pdf
[10] Joeris, B.: Connectivity, tree-decompositions and unavoidable-minors. Ph.D. Thesis (2015). http://hdl.handle.net/10012/9315
[11] Kurkofka, J.: The Farey graph is uniquely determined by its connectivity, J. Combin. Theory (Ser. B) 151, 223-234 (2021). doi:10.1016/j.jctb.2021.06.006. https://arxiv.org/abs/2006.12472 · Zbl 07396134
[12] Kurkofka, J.: Ubiquity and the Farey graph. Eur. J. Combin. 95, 103326 (2021). doi:10.1016/j.ejc.2021.103326. https://arxiv.org/abs/1912.02147 · Zbl 1466.05051
[13] Oporowski, B.; Oxley, J.; Thomas, R., Typical Subgraphs of 3- and 4-Connected Graphs, J. Combin. Theory (Ser. B), 57, 2, 239-257 (1993) · Zbl 0728.05041 · doi:10.1006/jctb.1993.1019
[14] Robertson, N.; Seymour, PD; Thomas, R., Excluding infinite minors, Discrete Math., 95, 1, 303-319 (1991) · Zbl 0759.05082 · doi:10.1016/0012-365X(91)90343-Z
[15] Robertson, N.; Seymour, PD; Thomas, R., Excluding subdivisions of infinite cliques, Trans. Am. Math. Soc., 332, 211-223 (1992) · Zbl 0774.05084 · doi:10.1090/S0002-9947-1992-1079057-3
[16] Seymour, PD; Thomas, R., Excluding infinite trees, Trans. Am. Math. Soc., 335, 597-630 (1993) · Zbl 0780.05015 · doi:10.1090/S0002-9947-1993-1079058-6
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.