Crux, space constraints and subdivisions
EUROCOMB’23
607–614
Bela Bollobás and Paul A. Catlin. Topological cliques of random graphs. Journal of Combinatorial Theory. Series B, 30(2):224-227, 1981.
https://doi.org/10.1016/0095-8956(81)90066-6
Bela Bollobás, Paul A. Catlin, and Paul Erdos. Hadwiger's conjecture is true for almost every graph. European Journal of Combinatorics, 1(3):195-199, 1980.
https://doi.org/10.1016/S0195-6698(80)80001-1
Béla Bollobás and Andrew Thomason. Proof of a conjecture of Mader, Erdos and Hajnal on topological complete subgraphs. European Journal of Combinatorics, 19(8):883-887, 1998.
https://doi.org/10.1006/eujc.1997.0188
Nikolaos Fountoulakis, Daniela Kühn, and Deryk Osthus. The order of the largest complete minor in a random graph. Random Structures & Algorithms, 33(2):127-141, 2008.
https://doi.org/10.1002/rsa.20215
John Haslegrave, Jie Hu, Jaehoon Kim, Hong Liu, Bingyu Luan, and Guanghui Wang. Crux and long cycles in graphs. SIAM J. Discrete Math., 36(4):2942-2958, 2022.
https://doi.org/10.1137/21M143488X
John Haslegrave, Jaehoon Kim, and Hong Liu. Extremal density for sparse minors and subdivisions. International Mathematics Research Notices, 2021.
https://doi.org/10.1007/978-3-030-83823-2_5
Seonghyuk Im, Jaehoon Kim, Younjin Kim, and Hong Liu. Crux, space constraints and subdivisions. arXiv preprint, arXiv:2207.06653, 2022.
Heinz Adolf Jung. Eine Verallgemeinerung des n-fachen Zusammenhangs für Graphen. Mathematische Annalen, 187:95-103, 1970.
https://doi.org/10.1007/BF01350174
János Komlós and Endre Szemerédi. Topological cliques in graphs. Combinatorics, Probability and Computing, 3(2):247-256, 1994.
https://doi.org/10.1017/S0963548300001140
János Komlós and Endre Szemerédi. Topological cliques in graphs. II. Combinatorics, Probability and Computing, 5(1):79-90, 1996.
https://doi.org/10.1017/S096354830000184X
Michael Krivelevich and Benjamin Sudakov. Minors in expanding graphs. Geometric and Functional Analysis, 19(1):294-331, 2009.
https://doi.org/10.1007/s00039-009-0713-z
Kazimierz Kuratowski. Sur le problème des courbes gauches en topologie. Fundamenta Mathematica, 15:271-283, 1930.
https://doi.org/10.4064/fm-15-1-271-283
Hong Liu and Richard Montgomery. A proof of Mader's conjecture on large clique subdivisions in C4-free graphs. Journal of the London Mathematical Society. Second Series, 95(1):203-222, 2017.
https://doi.org/10.1112/jlms.12019
Wolfgang Mader. Homomorphieeigenschaften und mittlere Kantendichte von Graphen. Mathematische Annalen, 174:265-268, 1967.
https://doi.org/10.1007/BF01364272
Wolfgang Mader. An extremal problem for subdivisions of K_5^{-}. Journal of Graph Theory, 30(4):261-276, 1999.
https://doi.org/10.1002/(SICI)1097-0118(199904)30:4<261::AID-JGT2>3.0.CO;2-Z
Joseph Samuel Myers. Graphs without large complete minors are quasi-random. Combinatorics, Probability and Computing, 11(6):571-585, 2002.
https://doi.org/10.1017/S096354830200531X
This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.
Copyright © 2023 Seonghyuk Im, Jaehoon Kim, Younjin Kim, Hong Liu